2013年武汉科技大学856数据结构（C语言版）A卷考研真题
考试科目代码及科目名称：856数据结构(C语言版)
答题内容写在答题纸上，写在试卷或草稿纸上一律无效考完后试题随答题纸交回。
考试时间3小时，总分值150分。
一、选择题（10小题，每题2分，共20分）
1．有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）
A．543612
B．453126
C．346521
D．234156
2．对有序表A[1..14]做二分查，查元素A[4]前被比较元素依次为（）。
A．A[1]，A[2]，A[3]
B．A[1]，A[14]，A[7]
C．A[7]，A[3]，A[5]
D．A[7]，A[5]，A[3]
利马科维奇3．下面几个符号串编码集合中，不是前缀编码的是（）。
A．{0，10，110，1111}
B．{11，10，001，101，0001}
C．{00，010，0110，1000}
D．{b，c，aa，ac，aba，abb，abc}
冒泡排序代码c语言
4．适用于折半查的表的存储方式及元素排列要求为（）。
A．链接方式存储，元素无序
B．链接方式存储，元素有序
C．顺序方式存储，元素无序c语言和python哪个更适合初学者
D．顺序方式存储，元素有序
5．最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。A．(rear+1)MODn=front
B．rear=front
C．rear+1=front
D．(rear-l)MODn=front
6．将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（）A．n-1
B．n
C．2n-1
D．2n
7．具有n个顶点、e条边的无向图的邻接矩阵中，零元素的个数为（）
A．e
B．2e
C．n2-2e
D．n2-1
8．某索引顺序表共有元素395个，平均分成5块。若先对索引表采用顺序查，再对块中元素进行顺序查，则在等概率情况下，分块查成功的平均查长度是（）A．43
B．79
civilization形容词
C．198
D．200
9．要以O（nlogn）时间复杂度进行稳定的排序，可用的排序方法是（）
A．归并排序
B．快速排序
C．堆排序
D．冒泡排序
10．设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，
则放入的位置是（）
A．8
免费自学电商教程B．3
C．5
D．9
二、填空题（10小题，每题2分，共20分）
1．下面程序段的时间复杂度为（）。(n>1)
sum=1；
for (i=0;sum<n;i++) sum+=1;
2．数据结构由数据的逻辑结构、存储结构和数据的（）三部分组成。
3．长度为11的有序表，采用折半查，在等概率情况下查成功的平均查长度为（）。
4．使用一个100个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队
空和队满，约定队头指针front等于队尾指针rear时表示队空。若为front=8，rear=6，则队列中的元素个数为（）。
5．将有关二叉树的概念推广到三叉树，一颗有244个结点的完全三叉树的深度为（）。
6．设一颗完全二叉树共有101个结点，它有（）叶子结点。
7．出栈操作时应判别栈是否（）。
8．带头结点的单链表Head为空的条件是（）。
9．快速排序的时间复杂度为（）。
10．某二叉树的先序和后序序列正好相反，则该二叉树一定是（）的二叉树。
三、判断题（10小题，每题2分，共20分）
1．数据元素是数据的最小单位。（）
2．折半查方法要求待查表必须是顺序存储结构的有序表。（）
3．当两个字符出现的频率相同时，则其哈夫曼编码也相同。（）
4．如果某种排序算法是不稳定的，则该算法是没有实际意义的。（）
5．将一棵树转换为二叉树后，根结点没有右子树。（）
6．串既可采用顺序存储，也可采用链式存储。（）
7．一个广义表的表尾总是一个广义表。（）
8．完全二叉树的叶子结点只可能在层次最大的一层上出现。（）
9．顺序存储结构的主要缺点是不利于插入或删除操作。（）
10．算法是对特点问题求解步骤的一种描述，因此它可以没有输入和输出。（）四、综合应用题（6小题，每题10分，共60分）
1．下表列出了某工序之间的优先关系和各工序所需时间。要求：
（1）画出AOE网
（2）列出各事件的最早开始时间、最迟开始时间
（3）出关键路径并指明完成该工程所需最短时间。
2．若一棵完全二叉树中叶子结点的个数为n，且最底层结点数≧2，则此二叉树的深度H=？
3．已知一颗二叉树的中序序列为BJFKDGAELIMHC，后序序列为JKFGDBLMIHECA，画出该二叉树的先序线索二叉树。
4．在n×n矩阵A中，所有下标值满足关系式i+j＜n+l的元素a ij(1≤i，j≤n)的值均为0，现将A中其它元素按行优先顺序依次存储到长一维数组sa中，其中元素a1，n存储在sa ［0］。
(1)设n=10，元素a4，9存储在sa［p］，写出下标p的值；
toggle是什么意思中文(2)设元素a i，j存储在sa［k］中，写出由i，j和n计算k的一般公式。
5．假定对有序表(1，9，15，21，24，35，52，54，61，65，97)进行折半查，试回答问题：
（1）画出描述折半查过程的判定树；
（2）分别求等概率情况下查成功和不成功时的平均查长度。
6．已知待排记录的关键字序列为{25，96，11，63，57，78，44}，请回答下列问题：
(1)写出堆排序的初始堆（大根堆）关键字序列；
写出堆排序1趟以后（交换与调整之后）的关键字序列；
(2)写出快速排序1趟以后的关键字序列；

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。