2012年河北工业大学数据结构与程序设计考研试题

数据结构真题2012年10月(总分：100.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.一个算法的时间耗费的数量级称为该算法的______（分数：2.00）A.效率B.难度C.可实现性D.时间复杂度√解析：[考点] 算法的时间复杂度的概念[解析] 一个算法的时间耗费的数量级称为该算法的时间复杂度。

2.顺序表便于______（分数：2.00）A.插入结点B.删除结点C.按值查找结点D.按序号查找结点√解析：[考点] 顺序表的特征[解析] 顺序表便于按序号查找结点。

3.设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是______（分数：2.00）A.p-＞next-＞next==headB.p-＞next==head √C.p-＞next-＞next==NULLD.p-＞next==NULL解析：[考点] 指针变量p指向尾结点的判定条件[解析] 单循环链表的指针变量p指向尾结点的判定条件是p-＞next==head。

4.设以数组A[0..m-1]存放循环队列，front指向队头元素，rear指向队尾元素的下一个位置，则当前队列中的元素个数为______（分数：2.00）A.(rear-front+m)%m √B.rear-front+1C.(front-rear+m)%mD.(rear-front)%m解析：[考点] 队列中元素个数的计算[解析] 队列中元素的个数为(rear-front+m)%m5.下列关于顺序栈的叙述中，正确的是______（分数：2.00）A.入栈操作需要判断栈满，出栈操作需要判断栈空√B.入栈操作不需要判断栈满，出栈操作需要判断栈空C.入栈操作需要判断栈满，出栈操作不需要判断栈空D.入栈操作不需要判断栈满，出栈操作不需要判断栈空解析：[考点] 顺序栈的性质的判断[解析] 入栈操作需要判断栈满，出栈操作需要判断栈空。

6.A是一个10×10的对称矩阵，若采用行优先的下三角压缩存储，第一个元素a 0，0的存储地址为1，每个元素占一个存储单元，则a 7，5的地址为______（分数：2.00）A.25B.26C.33D.34 √解析：[考点] 对称矩阵的元素的地址的计算[解析] 若对称矩阵采用下三角压缩存储，根据其地址的计算公式，可得到所求元素的地址。

河北工业大学2012年攻读硕士学位研究生入学考试试题参考答案（结构力学Ⅰ）一、是非题1. 02.×3. 04.×考点：1-3题考察静定结构、超静定结构的一般性质，4题考察组合结构的计算。

解析：1-3题请看下面编者语。

4题解答如下：AE 、EH 是梁式杆，AD 、DF 、FH 、CD 、GF 是链杆，故先求出支座反力、截断链杆DF 、解除E 点约束，取左半部分为研究对象,对E 点取距由0=∑E M 得：0223=⨯-⨯-⨯a F a P a P DF ，P F DF 2=，再根据D 结点的平衡可知：P N 21-=（求DF F 时也可以对A 点取距，根据对称性，E 结点的竖向力P 21，0=∑A M ，022/=⨯-⨯+⨯a F a P a P DF P F DF 2=）编者语：（1）关于静定结构、超静定结构的一般性质。

（2）关于组合结构的计算二、选择题1、B考点：影响线的应用中荷载最不利位置的确定。

解析：B R 的影响线如图所示：因必有一集中荷载在顶点，当48kN 力在顶点时，kN kN R B 682140148=⨯+⨯=，当40kN 力在顶点时，kN kN R B 721403248=⨯+⨯=，故kN R B 72=，选B 。

（选项中的C 选项分明是48kN+40kN=88kN 的结果，这只能是两力都加在B 上，而这是不可能的）。

编者语：关于荷载最不利位置的确定，有如下总结：最常见的、也是最重要的是上述2)、3)种情况，第5)种情况很少见，也可以说没有出过题目，故2)、3)情况必须要掌握，本题考察的是第2)种情况。

2.A考点：多跨静定梁的内力传递解析：当荷载作用于基本部分时，只有基本部分受力，附属部分不受力。

当荷载作用于附属部分时，则不仅附属部分受力，基本部分一般也受力。

本题中左边部分为主体结构，右边部分为附属结构，P力作用在主体结构上，右边附属结构不受力。

编者语：（1）有很多同学不明白，力作用在铰上，到底是作用在哪一边？我的回答是随便假设一边都可以算出相同的结果！现以此题来分析！由整体分析可知，水平力为零：当力作用在左边铰时：进一步解出：当力作用在右边铰时：进一步解出：故得出结论，对于集中荷载计算时，假设集中力作用在铰的任何一边都是可行的，故题目中直接把荷载加在铰上，但是要注意，当铰接处作用力偶时，应看清作用在铰的左侧还是右侧，力偶不能直接作用在铰上，只能作用在铰两侧的截面上。

A、 d,c,a,bB、
b,c,d,a C、
c,d,b,a D、
a,c,b,d
4、 若用一个大小为 6的数组来实现循环队列,且 当前 rear和 fr0矶 的值分别为 0和 3,当 从队列中删
除一个元素,再加入两个元素后,rear和 front的 值分别为多少?( )
A、 1和 5
B、 2和 4
C、 4和 2
11)装入下标范围为 0到 6的 Hash表 中,则该表中各关键字的次序为 (
)。
A、 72, 11, 37, 38, 56, 98, 48
B、 11, 48, 37, 38, 72, 98, 56
C、 98, 11, 37, 38, 72, 56, 48
D、 98, 56, 37, 38, 72, 11, 48
河北工业大学 2012年 攻读硕士学位研究生入学考试试题 [口 卷
科目名称 数据结构与程序设计
科目代码 80s 共 3 页
适用专业、领域
计算机技术 (专业学位)
注:所 有试题答案一律写在答题纸上,答 案写在试卷、草稿纸上-律 无效。
一、 填空题 (共 ⒛ 分,每空 2分 。答案一律写在答题纸上,否则无效。)
8 A、 B、 9 C、 10 D、 11
8、 高度为 6的满二叉树,总共具有的结点数是 ( )。
A、 15
B、 25
C、 20
D、 63
( 9、 树的后根遍历序列等同于该树对应的二叉树的
)
A、 先序序列 B、 中序序列 C、 后序序列
1O、 在一非空二叉树的中序遍历序列中,根结点的右边 ( )
A、 只有右子树上的所有结点
1、 写出下面稀疏矩阵的三元组表存储表示

)长 度相等的两个串一定是相等的。
60分 )
四 、 简 答 题 (共
1、
(6分 )如 果关键字是主关键字的话 ,则 对一个无序的数据元素序列经按主关键字排序后得到的 (8分 )由 于线性表的链式存储结构可 以见缝插针的有效地利用存储 空间,所 以线性表的链式存
结果是否是唯一 的?为 什么 ?
2、
储结构的存储密度大于线性表的顺序存储结构 ,这 种说法对吗 ?为 什么 ?
2分 。答 案 一 律 写在 答 题 纸 上 ,否 则 无 效 。 )
的两个数据元素 ,在 物理存储上赋予 位置的一种存
线性表的顺序映象就是逻辑上
储分配方式 。
2、
我们把图中所有顶点加上遍历时经过的所有边构成的子图称为
。
3、
在直接插入排序 、希尔排序 、直接选择排序 、堆排序 、快速排序和基数排序中 ,需 要 内存量最 。
( )虽 说静态链表是用数组来实现的,但 对其进行插入和删除操作时,却 并不涉及数组元素
查找快。
4、
的移动问题 。
5、
6、
( (
(
)线 性表的顺序存储结构是一种随机存取的存储结构 。 )二 叉排序树的形态与记录的读入顺序无关 。
)Hash表 查找是一种不需 比较或需很少 比较的查找方法 。
7、
8、
(
4、
均匀的 Hash函 数 ?
5、
(10分 )请 问什么是稳定排序 ?和 非稳定排序相 比,它 有什么优点 ?为 什么说快速排序 、希尔
(6分 )二 叉排序树 T的 各元素值均不相同,请 问用什么有效方法 ,才 能按递增次序打印出元素
(10分 )什 么是队列的假溢出?通 常可以采用什么办法解决假溢出?

图3
图4
该文档由天勤论坛（）整理，转载请注明出处
10. 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序下列排序方法
中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。
I．简单选择排序

II．希尔排序
III．快速排序
IV．堆排序
V．二路归并排序
图5
该文档由天勤论坛（）整理，转载请注明出处
【答案要点】 （1）算法的基本设计思想如下：
①分别求出 str1 和 str2 所指的两个链表的长度 m 和 n。 ②将两个链表表尾对其：令指针 p、q 分别指向 str1 和 str2 的头节点，若 m≥n，则使 p 指向链表中的第 m-n+1 个节点；若 m＜n，则使 q 指向链表中的第 n-m+1 个节点，即使指针 p、q 所指的节点到表尾的长度相等。 ③反复讲指针 p、q 同步后移，并判断他们是否指向同一节点（通过比较节点地址是否 相等，而不是比较节点值）。若 p、q 指向同一节点，则该节点即为所求的共同后缀的起始位 置。 （2）算法实现如下： typedef struct Node { char data; struct Node *next; }SNODE; SNODE *Findlist(SNODE *str1,SNODE *str2) { int m,n; SNODE *p,*q; m=Listlen(str1); n=Listlen(str2); for(p=str1;m>n;m--)
else return n*fact(n-1);
}
A．O(log2n)
B．O(n)
C．O(nlog2n) D．O(n2)
B。本算法是一个递归，设执行时间为 T(n)，则有：

2022年河北工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下列说法不正确的是（）。

A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13B.33C.18D.403、以下与数据的存储结构无关的术语是（）。

A.循环队列B.链表C.哈希表D.栈4、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。

A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front5、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。

A.（rear+1）MOD n=frontB.rear=frontC.rear+1=frontD.（rear-1）MOD n=front6、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4507、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝28、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。

A.CBEFDAB.FEDCBAC.CBEDFAD.不定9、设X是树T中的一个非根结点，B是T所对应的二叉树。

A）2k B） 2k-1 C）k D） 2k
25、从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A.O(1) B.O(n)
C.O(1Ogzn) D.O(n2)
26、在平衡二叉树中插入一个结点后造成不平衡，设最低的不平衡结点为A，并已知A的左孩子平衡因子为0，右孩子平衡因子为1，则应该做（ ）型调整以使其平衡
D．顺序访问相邻结点更灵活
48、已知关键字序列为{66，82，25，51，98，108}，利用快速排序方法，以第一个元素为基准得到的一趟排序结果为
A．{25，51，66，82，98，108}
B．{25，51，66，98，82，108}
C．{51，25，66，108，98，82}
41、在数据结构中，与所使用的计算机无关的是数据的 A 结构。
A．逻辑 B．存储 C．逻辑和存储 D．物理
42、若一个栈以数组V[0．．n-1]存储，初始栈顶指针top为n，则x入栈的正确操作是
A．top=top+1；V[top]=x B．V[top]=x；top=top+1
A）ABDECFG B）DBEAFCG
C）DEBFGCA D）GFCEBDA
38、通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 B 。
A．数据元素具有同一特点
B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致
C．每个数据元素都一样
B．p->prior = s；p->prior->next = s；s->next = p；s->prior = p->prior
C．s->next = p；s->prior = p->prior；p->prior = s；p->prior->next = s

单项选择题1.数据的（B）包括集合、线性、树和图4种基本类型A．存储结构B．逻辑结构C．基本运算D．算法描述2.对一个长度为n的顺序表，在第i个元素（1≤i≤n+1）之前插入一个新元素时需向右移动（B）个元素。

A．n-i B．n-i+1 C．n-i-1 D．i3下面程序的时间复杂度为（C ）。

For(i=0;i<m;i++)For(j=0;j<n;j++)A[i][j]=i*j;A.O(m2)B. O(n2)C. O(n*m)D.O(n+m)4长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（C）。

若没说明在第几个位置插入，则其复杂度为DA．O(0) B．O(1) C．O(n) D．O(n2) 5.数据结构就是研究（D ）。

A．数据的逻辑结构B．数据的存储结构C．数据的逻辑结构和存储结构D．数据的逻辑结构、存储结构及其数据在运算上的实现6下面关于算法的说法，错误的是（D）。

A．算法最终必须由计算机程序实现B．为解决某问题的算法和为该问题编写的程序含义是相同的C．算法的可行性是指指令不能有二义性D．以上三种说法都错误7线性表L=（a1，a2 ，……an，）下列说法正确的是（D ）。

A．每个元素都有一个直接前驱和一个直接后继B．线性表中至少要有一个元素C．表中所有元素的排列顺序必须是由小到大或由大到小D．除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和一个直接后继8．下面关于线性表叙述错误的是（ B ）。

A．线性表采用顺序存储，必须占用一段地址连续的单元B．线性表采用顺序存储，便于进行插入和删除操作C．线性表采用链式存储，不必占用一段地址连续的单元D．线性表采用链式存储，便于进行插入和删除操作9用链表表示线性表的优点是（C）A．便于随机存取B．存储空间比顺序存储方式少C．便于插入和删除D．数据元素的存储顺序与逻辑顺序相同10若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ D ）存储方式最节省时间。

一填空1.衡量算法效率的两个重要指标称为算法的______时间复杂度_和___空间复杂度2. 一个算法应具有有穷性，确定性，可行性，输入和输出这五个特性。

3. 线性表的长度是指___表中元素的个数___。

4. 在线性表的顺序存储中，元素之间的逻辑关系是通过元素存储的相对位置决定的；在线性表的链接存储中，元素之间的逻辑关系是通过相关元素的存储位置决定的。

5 在双向链表中，每个结点包含两个指针域，一个指向其直接前趋结点，另一个指向其直接后继结点。

二、判断题1．线性表的逻辑顺序与存储顺序总是一致的。

(FALSE)2．顺序存储的线性表可以按序号随机存取。

(TRUE)3．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

（FALSE）4．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

（TRUE）5．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。

（TRUE）6．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

（TRUE）三、单选题(请从下列A，B，C，D选项中选择一项)1．线性表是( ) 。

(A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空；(C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。

答：A2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。

插入一个元素时平均要移动表中的（）个元素。

(A) n/2 (B)（n+1）/2 (C) (n –1)/2 (D) n答：A3．线性表采用链式存储时，其地址( ) 。

(A) 必须是连续的；(B) 部分地址必须是连续的；(C) 一定是不连续的；(D) 连续与否均可以。

答：D4．用链表表示线性表的优点是（）。

(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同答：C5. 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。

参考答案：B
5.对有n个顶点、e条边且使用邻接表存储的有向图进行广度 优先遍历,其算法时间复杂度是 A. O(n) B. O(e) C. O(n+e) D. O(n*e)
参考答案：C
6.若用邻接矩阵存储有向图,矩阵中主对角线以下的元素均为 零,则关于该图拓扑序列的结论是 A.存在，且唯一 B.存在，且不唯一 C.存在，可能不唯一 D.无法确定是否存在
3.若一棵二叉树的前序遍历序列为 a,e,b,d,c,后序遍历序列为 b,c,d,e,a,则根结点的孩子结点
A.只有 e B.有 e、 b C.有 e、 c D.无法确定
参考答案：A
4.若平衡二叉树的高度为6,且所有非叶结点的平衡因子均为 1, 则该平衡二叉树的结点总数为 A. 12 B. 20 C. 32 D.33
参考答案：C
8. 下列关于最小生成树的叙述中,正确的是 I. 最小生成树的代价唯一 Ⅱ. 所有权值最小的边一定会出现在所有的最小生成树中 Ⅲ.使用普里姆 (Prim)算法从不同顶点开始得到的最小生成树一 定相同 IV. 使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生 成树总不相同 A. 仅 I B. 仅 Ⅱ C. 仅 I、 Ⅲ D. 仅 Ⅱ、Ⅳ
参考答案：C
7. 对如下有向带权图,若采用迪杰斯特拉 (Dijkstra) 算法求从源点a到其他各顶点的最短路径,则得到 的第一条最短路径的目标顶点是b,第二条最短路 径的目标顶点是 c,后续得到的其余各最短路径的 目标顶点依次是 A. d,e,f B. e,d,f C. f,d,e D. f,e,d
2012年全国硕士研究生入学统一考 试计算机学科专业基础综合试卷
数据结构部分
一、单项选择题：1~40小题。每小题2分，共80分。 在每小题给出的四个选项中，请选出一项最符合题 目要求的。

C）p=p->next->next; D） p->next=p;
17、若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（ D ）。
A）上三角矩阵 B) 稀疏矩阵
C) 对角矩阵 D) 对称矩阵
18、以下属于顺序存储结构优点的是（ A ）。
A）2i B）2i C）2i-1 D）2i-1
11、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。
A) 单链表 B) 仅有头指针的单循环链表
C) 双链表 D) 仅有尾指针的单循环链表
A）p->next=p->next->next; B） p=p->next;
C）p=p->next->next; D） p->next=p;
22、下面程序段的时间复杂度是( A )。
s =0;
for( i =0; i<n; i++)
for(j=0;j<n;j++)
A）顺序表 B）双链表 C）带头结点的双循环链表 D）单循环链表
38、已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ C ）。
A) 5，4，3，2，1，6 B) 2，3，5，6，1，4
C) 3，2，5，4，1，6 D) 1，4，6，5，2，3
C) s->next=hs; hs=s; D) s->next=hs; hs=hs->next;
35、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C ）。

《数据结构》考研真题及解答目录2009 年试题 (1)填空题 (1)解答题 (2)2010 年试题 (2)填空题 (2)解答题 (4)2011 年试题 (4)填空题 (4)解答题 (5)2012 年试题 (6)填空题 (6)解答题 (7)2013 年试题 (8)填空题 (8)解答题 (9)2014 年试题 (10)填空题 (10)解答题 (11)2015 年试题 (12)填空题 (12)解答题 (14)2009 年试题填空题1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是A.栈B.队列C.树D.图2.设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。

若每个元素出栈后立即进入队列 Q，且7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是A．1 B.2 C.3 D.43.给定二叉树图所示。

设 N 代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。

若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是A．LRN B.NRL C.RLN D.RNL4.下列二叉排序树中，满足平衡二叉树定义的是5.已知一棵完全二叉树的第 6 层（设根为第 1 层）有8 个叶结点，则完全二叉树的结点个数最多是A．39 B.52 C.111 D.1196.将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是I．父子关系II.兄弟关系III.u 的父结点与v 的父结点是兄弟关系A.只有IIB.I 和IIC.I 和IIID.I、II 和III7.下列关于无向连通图特性的叙述中，正确的是I．所有顶点的度之和为偶数II.边数大于顶点个数减1 III.至少有一个顶点的度为1A.只有IB.只有IIC.I 和IID.I 和III8.下列叙述中，不符合 m 阶B 树定义要求的是A．根节点最多有m 棵子树 B.所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接9.已知关键序列 5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字 3，调整后得到的小根堆是A．3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1910.若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序解答题41.（10 分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。

1线性表可用顺序表或链表存储。

试问：(1) 两种存储表示各有哪些主要优缺点(2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？(3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？2 针对带表头结点的单链表，试编写下列函数。

(1) 定位函数Locate：在单链表中寻找第i个结点。

若找到，则函数返回第i个结点的地址；若找不到，则函数返回NULL。

(2) 求最大值函数max：通过一趟遍历在单链表中确定值最大的结点。

(3) 统计函数number：统计单链表中具有给定值x的所有元素。

(4) 建立函数create：根据一维数组a[n]建立一个单链表，使单链表中各元素的次序与a[n]中各元素的次序相同，要求该程序的时间复杂性为O(n)。

(5) 整理函数tidyup：在非递减有序的单链表中删除值相同的多余结点。

3 设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递增有序的单链表。

要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。

表中允许有重复的数据。

4 设有一个表头指针为h的单链表。

试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。

要求逆转结果链表的表头指针h指向原链表的最后一个结点。

5 从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将链接方向逆转，如右图所示。

在图中的指针p指向当前正在访问的结点，指针pr指向指针p所指结点左侧的结点。

此时指针p所指结点左侧的所有结点的链接方向都已逆转。

(1) 编写一个算法，从任一给定的位置(pr, p)开始，将指针p右移1个结点。

如果p移出链表，则将p置为NULL，并让pr停留在链表最右边的结点上。

●__(4)__的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。

(4)A．树形存储结构B．链式存储结构C．索引存储结构D．散列存储结构●若循环队列以数组 Q[O..m-1] 作为其存储结构变量 rear 表示循环队列中队尾元素的实际位置，其移动按 rear=(rear+1) mod m 进行，变量 length 表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是__(5)__。

(5)A．rear-length B．(rear-length+m) mod mC．(1+rear+m-length) mod m D．m-length●一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有__(6)__个零元素。

(6)A．e B．2e C．n2-e D．n2-2e●若一棵哈夫曼(Huffman)树共有9个顶点，则其叶子结点的个数为__(7)__。

(7)A．4 B．5 C．6 D．7●若采用邻接矩阵来存储简单有向图，则其某一个顶点i的入度等于该矩阵__(8)__。

(8)A．第i行中值为1的元素个数 B．所有值为1的元素总数C．第i行及第i列中值为1的元素总个数D．第i列中值为1的元素个数●在—棵度为3的树中，若有2个度为3的结点，有1个度为2的结点，则有__(9)__个度为0的结点。

(9)A．4 B．5 C．6 D．7●设结点x和y是二叉树中任意的两个结点，在该二叉树的先根遍历序列中x在y之前，而在其后根遍历序列中x在y之后，则x和y的关系是__(10)__。

(10)A．x是y的左兄弟B．x是y的右兄弟C．x是y的祖先D．x是y的后裔●设顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。

若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找成功的平均查找长度为__(11)__。

(11)A．21 B．23 C．41 D．62DCDBDCCB(顺序查找平均查找长度是：（n+1）/2 (1+3)/2+(41+1)/2=23 123/3=41)●在一棵完全二叉树中，其根的序号为1，_(33)_可判定序号为p和q的两个结点是否在同一层。