数据结构考试题8.doc

数据结构考试题8
数据结构考试题8
数据结构考试题8
要求：所有的题目的解答均写在答题纸上，。
一、单项选择题(选择最准确的一项,共15小题，每小题2分，共计３０分）
1。　数据结构是指　 。
A．　一种数据类型
B.　数据的存储结构
Ｃ． 一组性质相同的数据元素的集合
D。 相互之间存在一种或多种特定关系的数据元素的集合
2。 以下算法的时间复杂度为 　 .
voiｄ　ｆun（iｎt ｎ)
{ﻩint　i＝１，ｓ=0;
ﻩwhilｅ （i＜＝n）
ﻩ｛ s+=ｉ＋100； ｉ++;　 ｝
｝
A． O（n)ﻩ ﻩ B. O（）
C。 O（nlog2ｎ） ﻩ ﻩﻩＤ． O（loｇ2n）
3。 在一个长度为ｎ的有序顺序表中删除其中第一个元素值为ｘ的元素时,在查找元素x时采用二分查找方法,此时删除算法的时间复杂度为 　.
A. O(n) ﻩ ﻩﻩﻩB．　O（nlog2n)
C。 Ｏ(n2) ﻩﻩＤ。 O(）
4． 若一个栈采用数组s[0..n-１］存放其元素，初始时栈顶指针为ｎ,则以下元素x进栈的正确操作是 　　 。
A。top++；s［top］＝x;ﻩ ﻩﻩ Ｂ。s［tｏp］＝x；ｔop++；
-－；ｓ［top]=x; ﻩﻩﻩ ［tｏp]=x；ｔoｐ—－；
5． 设环形队列中数组的下标为0～N-1，其队头、队尾指针分别为front和reａr(fｒｏnt指向队列中队头元素的前一个位置，reａr指向队尾元素的位置），则其元素个数为 。
A。 ｒeaｒ—fronｔﻩﻩ ﻩﻩﻩ B． ｒear-ｆrｏnｔ-1
C。　（rear－frｏnｔ）％N＋1 ﻩ Ｄ。 (rear—fｒont+Ｎ）%Ｎ
6． 若用一个大小为6的数组来实现环形队列,队头指针front指向队列中队头元素的前一个位置,队尾指针rear指向队尾元素的位置。若当前rear和ｆroｎt的值分别为0和３,当从队列中删除一个元素，再加入两个元素后，ｒear和front的值分别为
数据结构考试题8
数据结构考试题8
数据结构考试题8
。
A。 １和5ﻩ ﻩ ﻩ ﻩＢ． 2和4
C。 4和2 ﻩ ﻩ Ｄ。　5和１
７． 一棵高度为h（h≥1)的完全二叉树至少有 　 个结点.
Ａ。 2ｈ—1ﻩﻩ ﻩﻩ B。 2h
C. ２h+1 ﻩ ﻩﻩ ﻩD． 2h—1＋1
8。 设一棵哈夫曼树中有999个结点，该哈夫曼树用于对 　 个字符进行编码。
A。 ９99 ﻩﻩﻩ B。 499
Ｃ. 50０ﻩﻩ ﻩ ﻩﻩﻩD. 501
9. 一个含有ｎ个顶点的无向连通图采用邻接矩阵存储，则该矩阵一定是　　　 　.
A． 对称矩阵ﻩﻩ ﻩﻩ B。 非对称矩阵
C． 稀疏矩阵ﻩﻩ ﻩﻩ ﻩD. 稠密矩阵
10． 设无向连通图有ｎ个顶点e条边，若满足　 ，则图中一定有回路。
A。　ｅ≥n ﻩﻩﻩﻩ B。 e〈n－１
C． ｅ＝ｎ-1 ﻩﻩ ﻩﻩ D. 2e≥n
11。 如果从无向图的任一顶点出发进行一次广度优先遍