数据结构试卷
- 格式：doc
- 大小：91.00 KB
- 文档页数：8
南方医科大学
生物医学工程学院学年（）季学期考试
《数据结构》试卷（A卷）
姓名学号专业年级
1．数据结构的主要存储形式包括（ a ）。
A．顺序和链式结构B．逻辑和物理结构
C．具体和抽象结构D．理想和实际结构
2．线性表的顺序存储方式是按逻辑次序将元素存放在一片（ b ）的空间中。
A．地址任意B．地址连续C．单元大小不等D．无序
3．对链式存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。
插入一个元素时大约要移动表中的（d）个元素。
A．n B．n-1 C．n/2 D．0
4．若进栈序列为1，2，3，4，则（ b ）不可能是一个出栈序列。
A．3，2，1，4 B．4，2，3，1
C．3，2，4，1 D．4，3，2，1
5．字符串的替换操作replace (String &s, String &t, String &v)是指：若t是s的子串，则用串v替换串t在串s中的所有出现；若t不是s的子串，则串s不变。
例如，若串s为“aabbabcbaab cb acbab”，串t为“b c b”，串v为“abdc”，则执行replace操作后，串s中的结果
为（）。
A．aababdccbaabaaacabdc B．aababdcbaabaaacabdc C．aabbaabdcaaabdcacbab D．aabbabccbaabaaacabdc
6．已知广义表LS=(a,(b,c,d),e)，运用head和tail函数取出LS中原子d的运算是（）。
A．head（head（LS））B．tail（tail(head（LS））)
C．head（head（tail（LS）））D．tail(tail（head（tail（LS）））)
7．设有一个n n的对称矩阵A，为了节约存储空间，可以只存对角线及对角线以上的元素则需要的存储空间是（ a ）。
A．n * ( n+1 ) / 2 B．n-1 C．n2D．n/2
8．在有n个结点的哈夫曼树中，其非叶子结点的个数为（）。
A．不确定B．2n C．（n+1）/2 D．（n-1）/2
9．将一棵有100个结点的完全二叉树从根开始，每一层按照从左到右的次序进行编号，根结点的编号为1，则编号为48的结点的左孩子的编号为d树（ a ）。
A．96 B．97 C．98 D．99
10．设一个二叉树有n个结点，其中有n0个叶子结点，则它的度为2的结点的个数是（ b ）。
A．n-n0B．n0-1 C．n0+1 D．n/2-n0
11．在一棵树中，如果结点A有4个孩子，A的双亲是B，则A的度是（a ）。
A．4 B．5 C．6 D．7
12．图的生成树（d）。
A．与使用方法有关B．是唯一的C．有n棵D．有n-1棵
13．下面关于关键路径的说法，不正确的是（c）。
A．关键路径是从源点到汇点的最长路径B．关键路径不是回路
C．任意图的关键路径都只有一条D．关键路径上的活动不能耽搁
14．当一个图中边很稠密时，使用（）方法得到最小生成树比较节约时间。
A．Kruscal B．Prim C．深度优先D．广度优先
15．分块查找要求（）。
A．元素有序B．块内有序C．每块的大小相同D．块间有序
16．如果由于平衡二叉树的左子树的右子树上增加了结点而失去平衡，则应做（ c ）旋转。
A．左单B．右单C．先左后右D．先右后左
17．二分查找法要求查找表中各元素的值（）。
A．按值排好序B．按输入次序排列C．用链表表示D．用数组表表示
18．排序方法中平均性能最好的方法是（ c ）。
A．直接插入排序B．希尔排序C．快速排序D．基数排序
19．比较次数在初始序列为正序和逆序时没有差别的方法是（）。
A．直接插入排序B．胜者树排序C．冒泡排序D．快速排序
20．下列排序方法中不稳定的是（c ）。
A．归并排序B．冒泡排序C．希尔排序D．直接插入排序
请将答案填写在下表。
二、判断题
（ f ）21、算法的语句允许存在多义性。
（ t ）22、线性表采用链式存储时，其地址不一定是连续的。
（ f ）23、队列采用链式存储时，执行插入和删除操作的时间耗费很大。
（ f ）24、若一个栈的输入序列是：1，2，3，...,n ，输出序列的第一个元素是n ，则第i 个输出元素是n-i 。
（ ）25、串的长度是指串中字母的个数。
（ ）26、广义表的长度等于其中括号的层数。
（ ）27、稀疏矩阵可以用三元组法存储。
（ ）28、一个有4个结点的二叉树的形态有14种。
（ t ）29、具有8个结点的完全二叉树的深度为3。
（ f ）30、所有的满二叉树都是完全二叉树。
（ f ）31、树的先根遍历与相应二叉树的中序遍历结果相同。
（ f ）32、图中顶点的度的定义与树中结点的度的定义相同。
（ t ）33、有n 个顶点的有向图中边数最多为n 2。
（ t ）34、一个图有拓扑序列的充要条件是有向无环。
（ f ）35、二叉排序树是平衡二叉树。
（ t ）36、对平衡二叉树旋转的目的是使平衡因子越小越好。
（ f ）37、在二叉排序树中删除一个带有左右子树的结点，可以用它的右子树中序遍历下的第一个结点来代替。
（ ）38、当初始序列基本有序时，快速排序法所用时间最短。
（
f ）39、堆排序和归并排序的时间复杂度为O(n)。
（ f ）40、简单选择排序是稳定的排序方法。
三、综合题（共8题，第1小题2分，第2小题8分，其余各题每题5分）
41、分析下列各算法的时间复杂度：
i=1;
While(i<=n)
i=i*5;
o(n)
42、如下图所示，设双链表中指针p指着结点M，指针f指着将要插入的新结点X，写出代码，将X插在链表中两个数据元素M和N之间。
43、设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[4][7](10)存放在什么位置？脚注(10)表示用10进制表示。
711
44、假设一棵二叉树的前序序列为STWUV，中序序列为WUTVS，则它的后序序列是什么？要求画出二叉树。
uwvts
45．已知二叉树的形式如下图，请画出数组存储方式。
46．已知6个城市之间的距离关系如下图所示，要在它们之间建立5条光缆通路，应当怎样进行才使得材料需求量最小？
47．设散列表的长度m = 13；散列函数为H(K) = K mod m，给定的关键码序列为19，01，45，14，55，20，84，27，试画出用线性探查法解决冲突时所构造的散列表。
并求出在等概率的情况下，这种方法的搜索成功时的平均搜索长度。
0 1 2 3 4 5 6 7 8 9 10 11 12
48．下面是两个工程师的对话。
建国：今年的水文检测数据汇总来了，我们得找出最高的3个值。
兴华：一共有10000个数据，可以用EXCEL表格排序。
建国：可是这次的数据格式是顺序文件，要转换成EXCEL太费劲了。
兴华：也就是说得用C编程处理了。
建国：是啊，用什么排序方法好呢？
请你给出一个合理的排序解决办法，并画出最高的3个值的输出过程。
将问题简化，假设要处理的数据如下：
27，19，60，87，61，76，5，17。
