济南大学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