《数据结构》全真模拟试题与解答

全真模拟试题
一、单项选择题(在每个小题的 4 个备选答案中,选出正确的答案,并将其号码填在题后 的括号内。每小题 2 分,共 24 分) 1.一个具有 n 个顶点的无向完全图的边数为( ) ①n(n+1)/2 ②n(n-1)/2 ③n(n-1) ④n(n+1) 2.在索引顺序表中查找一个元素,可用的且最快的方法是( ) ①用顺序查找法确定元素所在块,再用顺序查找法在相应块中查找 ②用顺序查找法确定元素所在块,再用二分查找法在相应块中查找 ③用二分查找法确定元素所在块,再用顺序查找法在相应块中查找 ④用二分查找法确定元素所在块,再用二分查找法在相应块中查找 3.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个 元素,则采用( )存储方式最节省运算时间。 ① 单链表 ②双链表 ③带头结点的双循环链表 ④容量足够大的顺序表 4.串是( ) ①一些符号构成的序列 ②有限个字母构成的序列 ③一个以上的字符构成的序列 ④有限个字符构成的序列 5.堆排序在最坏情况下,其时间复杂性为( ) 2 ① O(nlog2n) ②O(n ) 2 ③O(log2n ) ④O(log2n) 6.快速排序的记录移动次数( )比较次数,其总执行时间为 O(nlog2n)。 ① 大于 ②大于等于 ③小于等于 ④小于 7.一棵二叉树有 n 个结点,要按某顺序对该二叉树中的结点编号, (号码为 1-n) ,编 号须具有如下性质:二叉树中任一结点 V,其编号等于其左子树中结点的最大编号加 1。 而其右子树中结点的最小编号等于 V 的编号加 1。试问应按( )遍历顺序编号。 ① 前根 ②中根 ③后根 ④层次 8.3 个结点可构成( )个不同形态的二叉树。 ① 2 ②3 ③4 ④5 9.对有 n 个记录的有序表采用二分查找,其平均查找长度的量级为( ) 2 ① O(log2n) ②O(nlog2n) ③O(n) ④O(n ) 10.对有 n 个记录的表按记录键值有序的顺序建立二叉树,在这种情况下,其平均查 找长度的量级为( ) ① O(n) ②O(nlog2n) ③O(1) ④(log2n) 11.栈操作的原则是( ) ① 先进先出 ②后进先出 ③栈顶插入 ④栈顶删除 12.设矩阵 A 是一对称矩阵(aij=aji,1<=i,j<=8),若每个矩阵元素占 3 个单元,将其上 三角部分(包括对角线)按行序为主序存放在数组 B 中,B 的首地址为 1000,则矩阵元素 a67 的地址为( ) ① 1031 ②1093 ③1096 ④1032 二、判断题(判断下列各题是否正确,正确在括号内打“√” ,错的打“×” 。每小题 1 分, 共 10 分) 1.如果两个串含有相同的字符,则这两个串相等。 ( ) 2. 数组可以看成线性结构的一种推广, 因此可以对它进行插入、 删除等运算。 ( ) 1 / 7

3.在索引顺序表上实现分块查找,在等概率查找情况下,其平均查找长度不仅与表 中元素个数有关,而且与每一块中元素个数有关。 ( ) 4.在顺序表中取出第 i 个元素所花费的时间与 i 成正比。 ( ) 5.在栈满情况下不能作进栈运算,否则产生“上溢” 。 ( ) 6.二路归并排序的核心操作是将两上有序序列归并为一个有序序列。 ( ) 7.对任意一个图,从它的某个顶点出发,进行一次深度优先或广度优先搜索,即可 访问图的每个顶点.( ) 8.二叉排序树或者是一棵空二叉树,或者是具有下列性质的二叉树:若它的左子树 非空,则根结点的值大于其左孩子的值;若它的右子树非空,则根结点的值小于其右孩子 的值。 ( ) 9.在执行某个排序算法过程中,出现了排序码朝着最终排序序列位置相反方向移动, 则该算法是不稳定的。 ( ) 10.一个有向图的邻接表和逆邻接表中表结点的个数一定相等。 ( ) 三、填空题(每空 2 分,共 26 分) 1.在带有头结点的单链表 L 中,若要删除第一个结点,则需执行下列三条语句:_ _______;L->next=U->next;free(U); 2.有一个长度为 20 的有序表采用二分查找方法进行查找,共有______个元素 的查找长度为 3。 3.采用冒泡排序对有 n 个记录的表 A 按键值递增排序,若 L 的初始状态是按键值递 增,则排序过程中记录的比较次数为_____。若 A 的初始状态为递减排列,则记录的 交换次数为_______。 4.在无头结点的双链表中,指针 P 所指结点是第一个结点的条件是______。 5.G 为无向图,如果从 G 的某个顶点出发,进行一次广度优先搜索,即可访问图的每 个顶点,则该图一定是_____图。 6.如果一个有向图中没有______,则该图的全部顶点可能排成一个拓扑序列。 7.深度为 8(根的层次号为 1)的满二叉树有______个叶子结点。 8. 将一棵有 100 个结点的完全二叉树按层编号, 则编号为 49 的结点 X, 其双亲 PARENT (X)的编号为_______。 9.设某闭散列表 HT 未满,散列函数 H(KEY)为键值第一字母在字母表中的序号,处 理冲突方法为线性探测法,请在下列算法划线处填上适当内容,以实现按键值第一字母的 顺序输出闭散列表中所有键值的算法。 void printword(keytype HT[m]) { for(i=1;i<=26;i++) { j=i; while(____________________) { if (____________________) printf(“datatype”,HT[j]); j=(j+1)% m; } } } 10.设有一个链队,结点结构为 data|next ,front 为队头指针,rear 为队尾指针, 当执行入队操作时需执行下列语句: malloc(p);p->data=x; p->next=NULL; ________________; 2 / 7

________________; 四、应用题(共 26 分) 1.有向图 G 的邻接表如下图所示,若删去图 G 中的边<V3,V6>和<V4,V5>,试 画出修改后图的邻接表。 (4 分)
顶点 入度

V1 V2 V3 V4 V5 V6

0 1 4 0 1 1 ^

2 3 6 3 3 ^ ^ ^

1

^

5

^

2.有向图如下图所示,写出以 V1 为出发点对图进行深度优先搜索所得到的所有可能 的访问序列。 (4 分) 1 3 6

2 5 4

3.对于键值序列(49,38,65,97,76,13,27,50) ,使用堆排序算法完成排序过程。要 求: ⑴画出初始堆(用二叉树表示) 。 ⑵画出分别输出 13,27 后重建的两个堆。 (5 分) 4.一个深度为 d(根的层次号为 1)的满 K 叉树有如下性质:第 d 层上的结点都是叶 子结点,其余各层上的每个结点都有 K 棵非空子树。如果从根这一层开始从左到右顺序逐 层对全部结点编号,且根结点的编号为 1,问编号为 n 的结点有右兄弟的条件是什么?其 右兄弟的编号是多少?(3 分) 5.给定权值{5,10,12,15,30,40} ,构造相应的哈夫曼树,要求写构造歩骤。 (4 分) 6 .已知一表为( Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec ),按表中顺 序依次插入初始为空的二叉排序树,要求: ⑴画出建立的二叉排序树。 (4 分) ⑵求出在等概率情况下查找成功的平均查找长度。 (2 分) 五、设计题(共 14 分) 1.设有一单链表 L,结点结构为 data|next ,结点个数至少 3 个,试画出链表 L 的结 构图,并编写算法判断该单链表 L 中的元素是否成等差关系,即:设各元素值次为 a1,a2,a3,…,an,判断 ai+1-ai=ai-ai-1 是否成立,其中 i 满足 2<=i<=n-1.(8 分) 2. 设有一棵二叉树以二叉链表作为存储结构, 结点结构为 lchild|data|rchild,其中 data 域中存放一个字符, 设计一个算法按前根遍历顺序仅打印出 data 域为数字的字符 (即 ‘0’<=data<=‘9’) (6 分)

3 / 7

全真模拟参考答案
一、单项选择题 1.② 2.③ 3.④ 4. ④ 5.① 6. .③ 7. ② 8. ④ 9. ① 10. ① 对键值有序的、具有 n 个记录的表来讲,当所建立的二叉排序树是一棵 深度为 n 的单支树时,在它上面的查找操作已经退化为顺序查找,所以其平均查找长 度的量级为 O(n). 11.② 12. ② 按题意要求, 将对称矩阵 A 的上三角部分按行优先进行存放数组了 B 中, 那么 B[k]与 aij 的对应关系为: 当 i<=j 时,k=(i-1)/2*(2*n-i+2)+j-i+1 因此有:k=(6-1)/2*(2*8-6+2)+7-6+1=32 故 LOC(a67)=LOC(a11)+(k-1)*l=1000+(32-1)*3=1093 二、判断题 1. × 2. × 3. √ 4. × 5. √ 6. √ 7. × 8. × 9. × 10. 三、填空题 1. U=L - > next 2. 4。 分析:二分查找的过程可以用一棵有序树来表示,该树第三层上有 4 个 结点,表示经过三次比较查找成功的元素个数为 4。 3. n-1、n(n-1)/2。 分析:采用冒泡排序时,若初始时已经自然有序,那么经 过一趟 n-1 次比较后,算法就自动终止了。若初始状态为递减排列,希望排序 成递增排列,则排序过程中比较一次,交换一次,总的比较、交换次数为 n(n-1)/2,其中 n-1 为趟数,n/2 为平均每趟的比较交换次数。 4. p - > prior = NULL。 5. 连通 6. 回路或环 7. 28-1 = 27 = 128 8. 24 9. HT[j]!=NULL 或 HT[j]不为空、H(HT[j])=I 10. rear - > next = p、rear = p 四、应用题 1. 修改后的有向图 G 的邻接表如图所示。

V1 V2 V3 V4 V5 V6
2.

0 1 4 0 0 0 ^ ^

2 3 ^

3

^

3 3

^ ^

1,2,5,4,3,6 4 / 7

1,3,6,4,5,2 1,3,5,4,6,2 3.⑴初始堆如图所示。
13 38 50 97 76 65 27 49

⑵输出 13 后重建的堆如图所示。
27 38 50 13 76 65 49 97

⑶输出 27 后重建的堆如图所示。
38 50 97 13 76 65 49 27

4.分析:在满 k 叉树中,除编号为 1 的根结点外,其余结点依次为每 k 个结点 拥有一个共同的双亲。比如: 第二号-第 k+1 号结点的双亲是第 1 号结点; 第 k+2 号-第 2k+1 号结点的双亲是第 2 号结点; 第 2k+1 号-第 3k+1 号结点的双亲是第 3 号结点; . . . . . . 从中可以看出,若编号为 n,那么当(n-1)%k = 0 时,它一定是某个结点的 最右边的孩子,即它的右边不会再有兄弟了。反之,当(n-1)%k≠0,它的右边一 定还有兄弟。 答案:编号为 n 的结点有兄弟的条件是(n-1)%k≠0,该点的右兄弟的编号是 n+1。 5.哈夫曼树的构造过程如图所示。 5 / 7

108

40

68

40 30

0 10 1111 1110 1100 1101

30

38

15 12

15

27

5
15

5

10

12

10

6.⑴建立的二叉排序树如图所示。

1 2 3 4 5 6 7 8 9 10 11 12
⑵在等概率情况下,查找成功的平均查找长度为 (1+2+3+4+5+6+...+12)/12 = 7*12/12 = 7。 五、设计题 1.单链表的结构图如图设计题Ⅱ 9.1.2 所示。

6 / 7

a1

a2

. . .

an



算法:int isrise (lklist L) { p = L -> next; b = p -> data – L -> data; while (p -> next != NULL) { q =p -> next; if (q -> data – p -> data !=b) return(0) else p = q; } return(1); } 2. Void Nchar (bitreptr t) { if (t != Null) { if (t -> data >= ’0’ ) && (t -> data <= ‘9’) printf (“%d” , t -> data ); Nchar (t -> lchild); Nchar (t -> rchild); } }

7 / 7


相关文档

  • 上海市育才中学2017-2018高一上10月月考数学试卷(图片版无答案)
  • 加强高中数学建模教学 培养学生的创新能力-最新教育资料
  • 湖南师范大学附属中学2016届高三月考(七)数学(理)试题 扫描版含解析_图文
  • 冀教版品德与生活一年级上册《我的第一个寒假》教学设计(1)
  • 如果数学学不好,那么物理、化学也不可能学好。在理工_图文
  • 1-2-1单位圆中的三角函数线
  • 2017学年高中数学人教A版选修2-3课后训练:1.3.2 “杨辉三角”与二项式系数的性质 Word版含解析
  • 西青区2011~2012学年度第二学期高二(文)科数学期末试卷
  • 当前信息技术在高中数学课堂教学中的具体应用-精选教育文档
  • 衡水中学2011—2012学年度第一学期期中考试高一数学试题+答案
  • 高二数学古典概率!!_图文
  • 电脑版