2012试卷_数据结构_A卷 下载本文

济南大学2012~2013学年第一学期课程考试试卷(A卷)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 E A F D H C G I B ……课 程 数据结构 授课教师 则结点I的双亲结点为:

… A) D B) H C) G D) C …10二叉树的第k层的结点数最多为( ).

…考试时间 201 年 月 日 考试班级 … A)2k-1 B)2K+1 C)2K-1 D)2k-1

…11已知一棵二叉树的中序遍历结果为DBHEAFICG,后序遍历结果为DHEBIFGCA,则该二叉…学 号 姓 名 …树的先序遍历的结果为:

… A) ADBHEFICG B) DHEBAIFGC C) ABDEHCFIG D) ABCDEFGHI …题号 一 二 三 四 总分 审核人 …12下面关于线性表的叙述错误的是( )。

… A) 线性表采用顺序存储必须占用一片连续的存储空间 …得分 … B) 线性表采用链式存储不必占用一片连续的存储空间 … C) 线性表采用链式存储便于插入和删除操作的实现 装…得 分 一、选择题(每小题2分,共40分)

D) 线性表采用顺序存储便于插入和删除操作的实现 …1 对顺序存储的线性表,设长度为n,在任何位置上插入或删除操作13执行一趟快速排序能够得到的序列是( )。 ……阅卷人 都是等概率的,删除一个元素时平均要移动表中的______个元素。

A) [41,12,34,45,27] 55 [72,63] … B) [45,34,12,41] 55 [72,63,27] …A)

n…2 B) n?12 C) n?12 D) n

C) [63,12,34,45,27] 55 [41,72] …2设一条单链表的头指针变量为head且该链表没有头结点,则其判空条件是( )。

D) [12,27,45,41] 55 [34,63,72]

……A) head==0 B) head->next==0 14设有6个结点的无向图,该图至少应有( )条边才能确保是一个连通图。 订C) head->next==head D) head!=0

A)5 B)6 C)7 D)8

……3用不带头结点的链接方式存储的队列,在进行插入运算时( ). 15按逐点插入法建立对应于序列(54,28,16,34,73,62,95,60,26,43)的二叉排序树后,查找62… A)仅修改头指针 B)头、尾指针都要修改 进行多少次比较。

…… C)仅修改尾指针 D)头、尾指针可能都要修改 A)2次 B)3次 C).5次 D)6次

…4已知广义表A=((a,b,c),(d,e,f)),从A中取出原子a的运算是_________。 16设一组初始记录关键字序列为(13,18,24,35,47,50,62,83,90,115,134),则利用二…… A) head(head(A))

分法查找关键字90需要比较的关键字个数为( )。 …B) head(tail(A))

A) 1 B) 2 C) 3 D) 4 …线 C) head(tail(tail(head(A))))

17两个字符串相等的充要条件是( )。 …D) head(head(tail(tail(A))))

A) 两个字符串的长度相等 B) 两个字符串中对应位置上的字符相等 ……5设有一个二维数组A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),每个元 C) 同时具备(A)和(B)两个条件 D) 以上答案都不对

…素占一个空间,问A[3][3](10)存放在什么位置?脚注(10)表示用10进制表示。 18设连通图G中的边集E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点……A)688 B)678 C)692 D)696

a出发可以得到一种深度优先遍历的顶点序列为( )。 …6设输入序列是1、2、3、……、n,经过栈的作用后输出序列的第一个元素是n,则输出序列中 A) abedfc B) acfebd C) aebdfc D) aedfcb …19下列程序段的时间复杂度为( )。

…第i个输出元素是( )。 … A) n-i B) n-1-i C) n+1-i D) 不能确定

for(i=0; i

……7在一棵树中,如果结点A有3个兄弟,而且B是A的双亲,则B的度为__________ for(i=0; i

A) O(m*n*t) B) O(m+n+t) C) O(m+n*t) D) O(m*t+n)

…20设在一棵度数为3的树中,度数为3的结点数有2个,度数为2的结点数有1个,度数为1…8 整数集合{8,4,5,7}构造的huffman树的带权路径长度为___________ …A) 24 B) 36 C) 48 D) 72

的结点数有2个,那么度数为0的结点数有( )个。 9有一棵二叉树的节点数据采用顺序存储结构,其存储情况如下所示: A) 4 B) 5 C) 6 D) 7

第1页,共3页

……………答……………题……………不……………要……………超……………过……………此……………线……………… 得 分

…阅卷人 二 填空题(每小题2分,共20分) 3对于下面的带权图,按照Kruskal算法生成最小生成树,画出算法执行过程中各步的状态。

…… 1设某棵完全二叉树中有100个结点,则该二叉树中有______________个叶子结点。

…2判断顺序循环队列队空的条件是_______

…… 3数据结构从逻辑上划分为三种基本类型:___________、__________、和___________。

… 4设一组初始关键字序列为(38,65,97,76,13,27,10),则第3趟冒泡排序结束后的结果为

… …_____________________。 … 5算法必须满足的5个重要特性是:有穷性、_________、_________、有输入和有输出。 … … 6对于一棵具有n个结点的二叉树,对应二叉链表中指针总数为__ __个。 … 7具有5个顶点的无向图,边的总数最多为______。 …… 8设某棵二叉树中度数为0的结点数为N0,度数为1的结点数为N1,则该二叉树中度数为2的 装结点数为_________ …… 9设某无向图中顶点数和边数分别为n和e,所有顶点的度数之和为d,则e=_______。 … 10已知链队列的头尾指针分别是f和r,则将值x入队的操作序列是_______。 ……

…得 分 三 分析题(每题7分,共30分)

……1有一个序列{53,17,12,61,98,70,87,25,63,46,14,59,

…阅卷人 67,75},用“除留余数法”设计一个哈希表,并填入下表,冲突采 …订用二次探测再散列。(6分)

……0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

4按照序列{24,36,10,17,12,30,60,19,8,50,40}输入顺序生成一棵二叉查找(排序)

… 树 …… …

… …… … 线…

…2假设某通信电文使用的字符集为{s,t,a,e,i},且每个字符在电文中出席的频率为{0.15,0.18,

……0.14,0.31,0.22},按Huffman算法构造并画出赫夫曼树,并按左分支为0右分支为1构造 …赫夫曼编码,要有构造赫夫曼树过程(图示即可)。 …… … …… … …… … ……

第2页,共3页

……………答……………题……………不……………要……………超……………过……………此……………线……………… ………………………

5 将由以下三棵树组成的森林转化成二叉树

D A E B C F

void MergeList_Sq(SqList La,SqList Lb,SqList *Lc)

G H I {

J K L M N O ElemType* pa=La.elem, pa_last; ElemType* pb=Lb.elem, pb_last;

P ……………答…… …… … …… 装 …… … …… … …… … …订 … …… … …… … ………得 分 线…阅卷人 ………… …… … …… … …… … ……

算法设计题(共5分)

设计一个把两个用顺序表存储的有序表合并的算法。(*Lc).listsize = (*Lc).length= ; ElemType* pc;

pc=(*Lc).elem=(ElemType*)malloc((*Lc).listsize*sizeof(ElemType)); if (!Lc.elem) exit(0); pa_last= ; pb_last=Lb.elem+Lb.length-1; while (pa<=pa_last&&pb<=pb_last) {

if(*pa<=*pb) ; else *pc++=*pb++; }

while ( ) *pc++=*pa++; while ( ) *pc++=*pb++; }

第3页,共3页

……………题……………不……………要……………超……………过……………此……………线………………

四1