一、选择题
1、下列说法不正确的是（ ）。
A.图的遍历是从给定的源点出发每个顶点仅被访问一次
B.遍历的基本方法有两种：深度遍历和广度遍历
C.图的深度遍历不适用于有向图
D.图的深度遍历是一个递归过程
2、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（ ）。
3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A.单链表 仅有头指针的单循环链表 双链表 仅有尾指针的单循环链表
4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（ ）。
A.（rear+1）MOD n=front
B.rear=front
C.rear+1=front
D.（rear-1）MOD n=front
5、下面关于串的叙述中，不正确的是（ ）。
A.串是字符的有限序列
B.空串是由空格构成的串
C.模式匹配是串的一种重要运算
D.串既可以采用顺序存储，也可以采用链式存储
6、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（ ）。
7、下列关于无向连通图特性的叙述中，正确的是（ ）。
Ⅰ．所有的顶点的度之和为偶数 Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1
A．只有Ⅰ．只有Ⅱ C．Ⅰ和Ⅱ．Ⅰ和Ⅲ
8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。
A.107 B.108 C.214 D.215
9、一个具有1025个结点的二叉树的高h为（ ）。
A.11 B.10 C.11至1025之间 至1024之间
10、就平均性能而言，目前最好的内排序方法是（ ）排序法。
A.起泡 希尔插入 交换 快速
二、填空题
11、分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是______算法，最费时间的是______算法。
12、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为______。
13、设单链表的结点结构为（data，next），next为指针域，已知指针px 指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y 插入结点x之后，则需要执行以下语句：______
14、VSAM（虚拟存储存取方法）文件的优点是：动态地______，不需要文件进行______，并能较快地______进行查找。
15、索引顺序文件既可以顺序存取，也可以______存取。
16、设广义表L=（（），（）），则head（L）是______； tail（L）是______；L的长度是______；深度是______。
17、已知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN（S，U）；ASSIGN（V， SUBSTR（S，INDEX（S，t），LEN（t）+1））； ASSIGN（m，’ww’），求REPLACE（S，V，m）=______。
18、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。
三、判断题
19、倒排序文件的优点是维护简单。（ ）
20、文件系统采用索引结构是为了节省存储空间。（ ）
21、稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）
22、广义表（（（a，b，c），d，e，f））的长度是4。（ ）
23、对于有n个结点的二叉树，其高度为log2n。（ ）
24、树形结构中元素之间存在一对多的关系。（ ）
25、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（ ）
26、在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（ ）
27、平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。（ ）
28、连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）
四、简答题
29、假定对有序表：（3，4，5，7，24，30，42，54，63，72，87， 95）进行折半查找，试回答下列问题：
（1）画出描述折半查找过程的判定树。
（2）若查找元素54，需依次与哪些元素比较?
（3）若查找元素90，需依次与哪些元素比较?
（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。
30、写出下列排序算法的基本思想，并写出对序列（23，12，35，47， 16，25，36，19，21，16）进行排序时每一趟的结果。
31、已知一个带有表头结点的单链表，结点结构为
假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：
（1）描述算法的基本设计思想。
（2）描述算法的详细实现步骤。
（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C＋＋或JAVA语言实现），关键之处请给出简要注释。
五、算法设计题
32、元素集合已存入整型数组A[1..n]中，试写出依次取A中各值A[i]（1≤i≤n）构造一棵二叉排序树T的非递归算法：CSBT（r，A）
33、对给定关键字序号j（1 35、二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部（注：向量d可视为循环表），其原则为，先将r[1]赋给d[1]，再从r[2]记录开始分二路插入。编写实现2-路插入排序算法。 参 一、选择题 1、【答案】C 2、【答案】A 3、【答案】D 4、【答案】B 5、【答案】B 6、【答案】D 7、【答案】A 8、【答案】B 9、【答案】C 10、【答案】D 二、填空题 11、【答案】起泡；快速 12、【答案】（n+1）/2 13、【答案】py->next=px->next；px->next=py 14、【答案】分配和释放存储空间；重组；对插入的记录@ 15、【答案】随机 16、【答案】（）；（（））；2；2 17、【答案】’xyxyxywwy’ 18、【答案】 【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s和t，则结点i和j在同一层上的条件是 三、判断题 19、【答案】× 20、【答案】× 21、【答案】√ 22、【答案】× 23、【答案】× 24、【答案】√ 25、【答案】× 26、【答案】× 27、【答案】× 28、【答案】√ 四、简答题 29、答：（1）判定树如图所示： （2） 若查找元素54，需依次和元素30、63、42、54比较，查找成功。 （3） 若查找元素90，需依次和元素30、63、87、95比较，查找失败。 （4） 30、答：此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，则再从后向前一趟排序，得到一个最小值。第一趟：12，23，35，16，25，36，19，21，16，47 第二趟：12，16，23，35，16，25，36，19，21，47 第三趟：12，16，23，16，25，35，19，21，36，47 第四趟：12，16，16，23，19，25，35，21，36，47 第五趟：12，16，16，19，23，25，21，35，36，47 第六趟：12，16，16，19，21，23，25，35，36，47 第七趟：12，16，16，19，21，23，25，35，36，47 31、答：（1）算法的基本设计思想定义两个指针变量p和q，初始时均指向头结点的下一个结点。p指针沿链表移动；当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到链表最后一个结点时，因为p和q相隔k，故q指针所指元素为倒数第k个结点。以上过程对链表仅进行一遍扫描。 （2）算法的详细实现步骤 ① count＝0，p和q指向链表表头结点的下一个结点。 ②若p为空，转⑤。 ③若count等于k，则q指向下一个结点；否则，count＝count＋1。 ④ p指向下一个结点，转步骤②。 ⑤若count等于k，则查找成功，输出该结点的data域的值，返回1；否则，查找失败，返回0。 ⑥算法结束。 （3）算法实现 五、算法设计题 32、答：算法如下： 33、答：算法如下： 34、答：算法如下： 35、答：算法如下： 下载本文
