发布时间 : 星期一 文章《数据结构》课程试卷（A卷）更新完毕开始阅读a077c411bf1e650e52ea551810a6f524ccbfcb96
《数据结构》课程试卷（A卷）
本试卷用于信息与电气工程系2004级计算机科学与技术专业学生
（时量：120分钟 总分：100分）
注意：1、答案必须填写在答题纸上，填写在试卷上的无效。
2、答案必须写明题目序号，并按题号顺序答题。 3、请保持行距，保持卷面整洁。
一、判断题（正确的画“√”，错误的画“×”。每题1分，共10分） 1、数据元素是数据的最小单位。
2、从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。 3、每种数据结构都应具备三种基本运算：插入、删除、查找。
4、对于同一组待输入的关键字集合，虽然各关键字的输入次序不同，但得到的二叉排序树都是相同的。
5、任何无环的有向图，其结点都可以排在一个拓扑序列中。 6、直接选择排序是稳定的。
7、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。
8、连通网的最小生成树是唯一的。
9、线性表采用链式存储结构，至少需要一个指针域。 10、二叉树一定是度为2的树。 二、选择题（每题2分，共30分）
1、线性表若采用链接方式存储时，要求内存中可用存储单元的地址（ ） A、必须是连续的 B、部分地址必须是连续的 C、连续或不连续都可以 D、一定是不连续的
2、采用顺序查找方法查找长度为n的顺序表时，等概率情况下，查找成功时的平均查找长度为（ ） A、n B、n/2 C、(n-1)/2 D、(n+1)/2
3、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q所指结点和p所指结点之间插入s所指结点，则执行（ ）
A、p->next=s；s->next=q； B、q->next=s；s->next=p；
C、p->next=s->next；s->next=p； D、s->next=p->next；p->next=s； 4、二维数组A[5][5]按行优先顺序存储，其中每个元素占2个存储单元。若A[0][0]的存储地址为400，则A[4][4]的存储地址为（ ） A、450 B、448 C、446 D、444
5、设循环单链表中结点的结构为（data，next）,且rear是指向非空的带头结点的循环单链表的尾结点的指针。若想删除链表中第一个结点，则应执行（ ） A、s=rear；rear=rear->next； delete s； B、rear=rear->next；delete rear；
C、rear=rear->next->next；delete rear；
1
D、s=rear->next->next；rear->next->next=s->next；delete s； 6、一个栈的入栈序列为a，b，c，则出栈序列不可能的是（ ）
A、c,b,a B、b,a,c C、c,a,b D、a,c,b
7、在长度为n的线性表中，在第i个元素之前插入一个新的元素x，需要移动（ ）个元素。
A、n B、n-i+1 C、n-i D、i+1
8、某二叉树的先序和后序序列正好相反，则该二叉树一定是（ ）的二叉树。 A、高度等于其结点数 B、空或只有一个结点 C、任一结点无左孩子 D、任一结点无右孩子 9、具有35个结点的完全二叉树的深度为（ ） A、5 B、6 C、7 D、8 10、对线性表进行折半查找时，要求线性表必须（ ）
A、以链接方式存储且结点按关键字有序排列 B、以顺序方式存储 C、以顺序方式存储且结点按关键字有序排列 D、以链接方式存储 11、我们将由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论（ ）是正确的。
A、树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B、树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C、树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D、以上都不对
12、具有n个顶点的有向图最多有（ ）条边。
A、n B、n(n-1) C、n(n+1) D、n2
13、正常情况下，删除非空的顺序栈的栈顶元素，栈顶指针TOP的变化是（ ） A、TOP不变 B、TOP←0 C、TOP←TOP+1 D、TOP←TOP-1 14、若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（ ）
A、9 B、11 C、12 D、不确定 15、下列排序法中速度最快的是（ ）
A、直接插入排序 B、直接选择排序 C、冒泡排序 D、堆排序 三、填空题（每空2分，共20分）
1、一个算法应具有有穷性、确定性、________、输入和________。 2、设有广义表D=(a,(b,c)),其表头为________，表尾为________。
3、如果一棵深度为k的二叉树中，只有度为0和度为2的结点，则该二叉树至少有________个结点，至多有________个结点。
4、在有向图的邻接矩阵中，第i个顶点的出度等于________，第i个顶点的入度等于________。图的弧数等于________。
5、具有7个叶子结点的哈夫曼树（Huffman）的结点总数为__________。 四、综合应用题（共40分） 1、画出下图的最小生成树。（3分）
1 5 8
3 3 15 2
10
12 6 6 9 4 2 7 7 5 2
2、已知一个稀疏矩阵的三元组表为：
行数md=5，列数nd=5，非零元素个数td=4，其三元组表为： 行号 列号 非零元素值 0 0 15 1 4 11 2 3 6 3 2 91
根据上述三元组表，把矩阵还原。（3分）
3、已知一棵二叉树的先序遍历序列为ABECDFGHIJ, 中序遍历序列为EBCDAFHIGJ, 试画出这棵二叉树，并给出这棵二叉树的后序遍历序列。（5分）
4、某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.31，0.07，0.09，0.14，0.23，0.03，0.11。（1）画出对应的Huffman树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求其带权路径长度WPL。（2）设计Huffman编码。（6分）
5、求出下图中从0号顶点到其余各顶点的最短路径，并计算路径长度。（5分） 80 3 1 15 40 60 30 32 5 0 100 50 45 2 4 90
6、已知一组元素为（25,13,15,31,7,20,37），按输入顺序逐个插入结点，建立一棵初始为空的二叉排序树，并分别对它进行中序遍历和层次遍历。（5分）
7、已知一组关键字为（19，14，23，1，68，20，84，27，55，11），哈希表表长为m=15，采用除留余数法构造哈希函数H(key)，采用线性探测法处理冲突。试构造此哈希表，并计算等概率情况下查找成功时的平均查找长度ASL。（5分）
8、给出一组关键字K=（12，2，16，30，8，28，4，10，20，6，18）， 希望排序为非递减序列。试写出： （8分）
（1）快速排序（选第一个记录为枢轴）的第一趟排序结果。
（2）采用堆排序，画出：①初始（大顶）堆；②第一次输出堆顶后调整建成的新堆。
3
《数据结构》课程试卷（A卷）标准答案
本试卷用于信息与电气工程系2004级计算机科学与技术专业学生
（时量：120分钟 总分：100分）
一、判断题（正确的画“√”，错误的画“×”。每题1分，共10分） 1、× 2、√ 3、√ 4、× 5、√
6、× 7、× 8、 √ 9、√ 10、× 二、选择题（每题2分，共30分）
1—5：CDBBD 6—10：CBABC 11—15：ABCBD 三、填空题（每空2分，共20分） 1、可行性，输出 2、a，((b,c)) 3、2k-1，2k-1
4、第i行中非零元素(“1”)的个数 第i列中非零元素(“1”)的个数
邻接矩阵中所有非零元素(“1”)个数之和。 5、13
四、综合应用题（共40分）
1、 1 5
3 3 15 2
7 4 2 6
7 6
2、
15 0 0 0 0 0 0 0 0 11 0 0 0 6 0 0 0 91 0 0 0 0 0 0 0 3、 A B F E G C D H
I
5 J 4
后序序列为：EDCBIHJGFA 4、 WPL=2.78
各字符的出现频率及对应的Huffman编码： 0.05 10111 23 31 0.31 11 0.07 1010 9 11 14 0.09 000 0.14 100 7 0.23 01 0.03 10110
3 5 0.11 001
5、0号顶点到其余各顶点的最短路径及路径长度如下： 0—>1 （0，1） 40 0—>2 （0，2） 50 0—>3 （0，1，3） 120 0—>4 （0，1，4） 100 0—>5 （0，1，3，5） 135 6、
25 中序序列为：7，13，15，20，25，31，37
31 层次序列为：25，13，31，7，15，37，20 13
37 7 15
20
7、 14 1 68 27 55 19 20 84 23 11 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ASL成功=(1*6+2+3+4+3)/10=1.8 8、（1）快速排序的第一趟排序结果：
{6，2，10，4，8} 12 {28，30，20，16，18}
（2）①初始（大顶）堆（如左上方图所示） ②第一次输出堆顶后调整建成
的新堆（如右下方图所示） 30 20 12 10 2 6 18 16 8 28 20 12 10
5 28 4 16 18 8 30 4 2 6