专升本 专业课习题.pdf

专升本《数据结构》试卷2
一、单项选择题：（每小题2分，共10分）
对于下列各题，在备选答案中选出一个正确的，并将其编号填在“”位置上。
1.折半查找法要求查找表中各元素的键值必须是。
A.递增或递减B.递增C.递减D.无序
2.若对某线性表最常进行的操作是在最后一个元素之后插入和删除第一个元素，则采用
存储方式最节省运算时间。
A.单链表B.双链表
C.仅有头指针的单循环链表D.仅有尾指针的单循环链表
3.有64个结点的完全二叉树的深度为（假设根结点的层次为1）。
A.8B.7C.6D.5
4.对于键值序列（2，33，21，18，65，38，7，49，24，86），用筛选法建堆，必须从键值
为的结点开始。
A.86B.2C.65D.38
5.设图G用邻接表存储，则求每个顶点入度的算法时间复杂度为。
A.O(n)B.O(n+e)C.O(n*n)D.O(n*e)
二、判断题：（每小题2分，共10分）
判断下列各题是否正确，若正确，在题后的括号内填“T”，否则填“F”。
1.在队满情况下不能作入队处理，否则，将产生“上溢”。（）
2.基于插入思想的排序算法都是稳定的。（）
3.一个有向图的邻接表和逆邻接表中的结点个数不一定相等。（）
4.若一棵二叉树的任一非叶子结点度为2，则该二叉树为满二叉树。（）
5.广义表是线性表的推广，因此也可以采用顺序方式进行存储。（）
三、填空题：（每小题2分，共10分）
1.在单链表中，删除指针P所指结点的后继结点的语句是：。
2.有向图G用邻接矩阵A[1..n，1..n]存储表示，其第i行的所有元素之和等于顶
点i的。
3.基数排序算法的时间复杂度为。
4.平衡二叉树中每个结点的平衡因子定义为。
5.利用直接插入排序算法对有n个元素的数据表进行排序，在最坏情况下，元素的
移动次数为。
四、解答下列各题：（每小题10分，共40分）
1.写出采用顺序方式存储的栈的类型描述及相应的入栈、出栈操作的示意图。
2.已知数据表为（60，20，31，5，44，55，61，30，80，150，4，29），写出采用希尔排
序算法进行排序的详细过程和结果（假设增量序列dlta[]={6,3,1}）。
3.已知图G的邻接表存储结构示意图如下所示，画出它的逻辑关系示意图，以及按深度
优先搜索和广度优先搜索进行遍历所得到的顶点序列。
4.设散列函数为H(K)=Kmod5，散列表的地址空间为0..6，初始时散列表为空，用线性
探测法解决冲突，请写出依次插入23，14，9，6，30，12，18时散列地址的计算过程及结
果，以及最后得到的散列表。
五、算法设计题：（前两题必做，每题15分，共30分；第三题为附加题，选做，10分）
1.设计算法将一个带头结点的单循环链表A分解为两个具有相同结构的链表B、C，其中：
B表中的结点为A表中元素的顺序号为奇数的结点，而C表中的结点为A表中元素的
顺序号为偶数的结点。（要求利用原表结点。）
2.已知S为顺序栈。写出S的存储结构类型描述。试编写算法实现将元素x插入栈S
的入栈操作Push(S,x)和删除栈顶元素的出栈操作Pop(S)。
3.已知一棵完全二叉树存于顺序表sa中，sa.elem[1..sa.last]包含各结点值。试编写算法
根据此顺序存储结构建立该二叉树的二叉链表T。
专升本《数据结构》试卷1
一、填空题：（每小题2分，共10分）
1.设有数据结构（D，R），其中D是数据元素的有限集，R是的有限集。
2.深度为k的二叉树其结点数至多有个。
3.栈是一种特殊的线性表，它允许在表的一端进行操作。
4.通常象交通、道路问题的数学模型是一种称为的数据结构。
5.哈希表是一种查找表，可以根据哈希函数直接获得。
二、单项选择题：（每小题2分，共10分）
对于下列各题，在备选答案中选出一个正确的，并将其编号填在“”位置上。
1.若线性表最常用的操作是存取第i个元素及其前驱元素的值，则采用存储方式最
节省运算时间。
A.单链表B.双链表C.单循环链表D.顺序表
2.下列排序算法中，算法在进行一趟相应的排序处理结束后不一定能选出一个元素
放到其最终位置上。。
A.直选择排序B.冒泡排序C.归并排序D.堆排序
3.队列的操作原则是。
A.先进后出B.先进先出C.只能进行插入D.只能进行删除
4.在具有n个结点的二叉链表中，非空的链域个数为。
A.n-1B.nC.n+1D.不确定
5.对具有n个元素的有序查找表采用折半查找算法查找一个键值，其最坏比较次数的数
量级为。
A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)
三、判断题：（每小题2分，共10分）
判断下列各题是否正确，若正确，在题后的括号内填“T”，否则填“F”。
1.在栈为空的情况下不能作出栈处理，否则，将产生下溢出。