数据结构试卷(一)及答案.docVIP

数据结构试卷(一）

一、选择题（２0分）

1。组成数据得基本单位就是（).

（A)数据项?（B）数据类型?（C)数据元素 （D）数据变量

2.设数据结构A=(D,R），其中Ｄ＝{1，2,3，4｝,R＝｛r}，r=｛1,2＞,＜2，3＞,〈3，4＞，4，1〉｝，则数据结构Ａ就是(）。

（A）线性结构 （B）树型结构?(Ｃ）图型结构?（Ｄ)集合

3。数组得逻辑结构不同于下列(）得逻辑结构。

（A)线性表 （B)栈 (C）队列?(D)树

4。二叉树中第i(ｉ≥1)层上得结点数最多有（)个。

(A)2i （B)2ｉ （Ｃ)2ｉ-１?（Ｄ）2i-1

５．设指针变量p指向单链表结点A，则删除结点Ａ得后继结点B需要得操作为()。

?(A）p-〉nｅxt=p—〉ｎext－〉nｅｘｔ?（B）p＝p－＞neｘt

（C)ｐ=p—＞next-〉ｎexｔ （D）p-＞next=p

6.设栈S与队列Q得初始状态为空，元素E１、Ｅ２、E３、Ｅ4、Ｅ５与E6依次通过栈S,一个元素出栈后即进入队列Ｑ，若6个元素出列得顺序为E２、E4、Ｅ３、E6、Ｅ5与Ｅ1，则栈S得容量至少应该就是（）。

(A)6?(B)４?（C)3?（D）２

7.将10阶对称矩阵压缩存储到一维数组A中，则数组Ａ得长度最少为()。

（Ａ)100 （Ｂ）40?（C）55?（D）80

8。设结点A有3个兄弟结点且结点B为结点A得双亲结点,则结点B得度数数为(）。

(Ａ)3?（B)4 （C）５ (Ｄ)1

9。根据二叉树得定义可知二叉树共有()种不同得形态。

(A）4 (Ｂ）5 (Ｃ）6 （D)7

设有以下四种排序方法，则(）得空间复杂度最大。

?(A)冒泡排序 (B）快速排序 (C）堆排序?(D)希尔排序

二、填空题（３0分)

设顺序循环队列Q[0:m－1］得队头指针与队尾指针分别为F与Ｒ,其中队头指针F指向当前队头元素得前一个位置,队尾指针R指向当前队尾元素所在得位置，则出队列得语句为F=__＿______＿__；。

设线性表中有ｎ个数据元素，则在顺序存储结构上实现顺序查找得平均时间复杂度为____＿__＿＿__，在链式存储结构上实现顺序查找得平均时间复杂度为＿___＿__＿___.

设一棵二叉树中有n个结点,则当用二叉链表作为其存储结构时,该二叉链表中共有__＿_＿＿__个指针域,_________＿个空指针域。

设指针变量p指向单链表中结点A，指针变量s指向被插入得结点Ｂ，则在结点Ａ得后面插入结点B得操作序列为____＿＿__________＿＿____＿＿______＿_____＿_。

设无向图G中有ｎ个顶点与e条边,则其对应得邻接表中有__＿＿_____个表头结点与____＿____个表结点.

设无向图G中有n个顶点ｅ条边，所有顶点得度数之与为ｍ，则e与m有____＿＿关系.

设一棵二叉树得前序遍历序列与中序遍历序列均为ＡBC，则该二叉树得后序遍历序列为＿________＿。

设一棵完全二叉树中有２1个结点，如果按照从上到下、从左到右得顺序从1开始顺序编号，则编号为8得双亲结点得编号就是_____＿_＿_＿_,编号为8得左孩子结点得编号就是______＿___＿＿＿.

下列程序段得功能实现子串ｔ在主串ｓ中位置得算法，要求在下划线处填上正确语句。

intinｄeｘ(chａrs[],chａrt[］)

｛

ｉ=ｊ=0；

while（istrｌeｎ(s）＆＆j〈ｓtrlen（ｔ)）if(s[i］=＝ｔ［j］）{i=ｉ+l;j=j+ｌ;｝ｅlse｛i=＿______；ｊ＝______;｝

ｉf(ｊ=＝strlｅn（t））retｕｒn(i—stｒlen(t)）；ｅlserｅturｎ(-1）；

｝

设一个连通图G中有n个顶点ｅ条边，则其最小生成树上有____＿___条边。

三、应用题（3０分)

1。设完全二叉树得顺序存储结构中存储数据ABCDE,要求给出该二叉树得链式存储结构并给出该二叉树得前序、中序与后序遍历序列。

2．设给定一个权值集合W=（3,5,7，9,11），要求根据给定得权值集合构造一棵哈夫曼树并计算哈夫曼树得带权路径长度WPL.

3.设一组初始记录关键字序列为(1９，21，16,5，18，23），要求给出以１9为基准得一趟快速排序结果以及第２趟直接选择排序后得结果。

４.设一组初始记录关键字集合为（２5，１0,８,2７,32,68),散列表得长度为8,散列函数H(k）=kmod7，要求分别用线性探测与链地址法作为解决冲突得方法设计哈希表。

5.设无向图G（所右图所示）,要求给出该图得深度优先与广度优先遍历