完全二叉树 D. 堆
13．连续存储设计时，存储单元的地址（ ）。
A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续
14．以下属于逻辑结构的是（ ）。
A．顺序表 B. 哈希表 C.有序表 D. 单链表
二、判断题
1. 数据元素是数据的最小单位。( )
2. 记录是数据处理的最小单位。 ( )
3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( )
4．算法的优劣与算法描述语言无关，但与所用计算机有关。( )
5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( )
6．算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。( )
7．程序一定是算法。( )
8．数据的物理结构是指数据在计算机内的实际存储形式。( )
9. 数据结构的抽象操作的定义与具体实现有关。( )
10. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。( )
11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )
12. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。( )
13. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. ( )
三、填空题
1．数据的物理结构包括 的表示和 的表示。
2. 对于给定的n个元素,可以构造出的逻辑结构有
（1） ，
（2） ，
（3）
，__
（4）_四种。
3．数据的逻辑结构是指 。
4．一个数据结构在计算机中 称为存储结构。
5．抽象数据类型的定义仅取决于它的一组_
_（1）_，而与
_（2）_无关，即不论其内部结构如何变化，只要它的
_（3）_不变，都不影响其外部使用。
6．数据结构中评价算法的两个重要指标是
7.
数据结构是研讨数据的_
（1）_和
_（2）_，以及它们之间的相互关系，并对与这种结构定义相应的_
（3）_，设计出相应的
（4）_。
8． 一个算法具有5个特性:
（1） 、
（2） 、
（3）
，有零个或多个输入、有一个或多个输出。
9．已知如下程序段
FOR i:= n DOWNTO 1 DO {语句1}
BEGIN
x:=x+1； {语句2}
FOR j:=n DOWNTO i DO {语句3}
y:=y+1; {语句4}
END；
语句1执行的频度为
（1） ；语句2执行的频度为
（2） ；语句3执行的频度为
（3）
；语句4执行的频度为
（4） 。
10．在下面的程序段中，对ｘ的赋值语句的频度为______（表示为n的函数）
FOR i：＝１ TO n DO
FOR j：＝１ TO i DO
FOR k：＝1 TO j DO
ｘ：＝ｘ＋delta；
11.下面程序段中带下划线的语句的执行次数的数量级是：
i：=1； WHILE i<n DO
i：=i*2;
12. 下面程序段中带下划线的语句的执行次数的数量级是( )。
i:=1;
WHILE i<n BEGIN FOR j:=1 TO n DO
x:=x+1;i:=i*2 END；
13. 下面程序段中带有下划线的语句的执行次数的数量级是( )
i：=n*n WHILE i<>1 DO
i:=i div 2;
14. 计算机执行下面的语句时，语句s的执行次数为 _______ 。
FOR(i=l；i<n-l；i++)
FOR(j=n;j>=i;j--)
s;
15. 下面程序段的时间复杂度为________。(n>1)
sum=1；
for (i=0;sum<n;i++) sum+=1;
16．设m.n均为自然数，m可表示为一些不超过n的自然数之和，f(m,n)为这种表示方式的数目。例f(5,3)=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。
①以下是该函数的程序段，请将未完成的部分填入，使之完整
int f(m,n)
int m,n;
{ if(m==1)
return
(1) ;
if(n==1){
return
(2) ;}
if(m<n)
{return f(m,m);}
if (m==n)
{return 1+
(3) ;}
return f(m.n-1)+f(m-n,
(4) );
}
②执行程序，f(6,4)= 。
17. 在有n个选手参加的单循环赛中，总共将进行______场比赛。
四．问答及应用
1什么是数据 它与信息是什么关系
2什么是数据结构 有关数据结构的讨论涉及哪三个方面
3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、 栈、队列、优先级队列等;
非线性结构包括树、图等、这两类结构各自的特点是什么？
4 什么是抽象数据类型？试用C++ 的类声明定义“复数”的抽象数据类型。要求
(1) 在复数内部用浮点数定义它的实部和虚部。
(2)
实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。
(3) 定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。
(4) 定义重载的流函数来输出一个复数。
5 用归纳法证明：
(1)
(2)
(3)
6 什么是算法 算法的5个特性是什么 试根据这些特性解释算法与程序的区别。
7 设
n为正整数, 分析下列各程序段中加下划线的语句的程序步数。
(1)
for (
int i = 1
; i <= n
; i++) (2)
x = 0
; y = 0
;
for (
int j = 1
; j <= n
; j++)
{
for (
int i = 1
; i <= n
; i++)
c[i][j] = 0.0
; for (
int j = 1
; j <=
i
; j++)
for (
int k = 1
; k <= n
; k++)
for (
int k = 1
; k <= j
; k++)
c[i][j] = c[i][j] + a[i][k] * b[k][j]; x =
x + y;
}
(3)
int i = 1
, j = 1
; (4)
int i
=1
;
while (i<=n
&& j<=n)
{ do
{
i = i + 1; j = j + i
; for (
int j
= 1
; j <= n
; j++)
} i = i + j;
} while ( i < 100 + n )
;
8 试编写一个函数计算n!*2n的值，结果存放于数组A[arraySize]的第n个数组元素中，0 ￡ n ￡
arraySize。若设计算机中允许的整数的最大值为maxInt，则当n > arraySize或者对于某一个k (0 ￡ k
￡ n)，使得k!*2k > maxInt时，应按出错处理。可有如下三种不同的出错处理方式：
(1) 用
cerr <<及
exit (1)语句来终止执行并报告错误；
(2) 用返回整数函数值0, 1来实现算法，以区别是正常返回还是错误返回；
(3) 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。
试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。
9 (1) 在下面所给函数的适当地方插入计算count的语句：
void d (ArrayElement x[ ]
, int n )
{
int i = 1
;
do {
x[i] += 2
; i += 2
;
} while (i <= n )
;
; i = 1
;
while ( i <= (n / 2) )
{
x[i] += x[i+1]
; i++
;
}
}
(2) 将由(1)所得到的程序化简。使得化简后的程序与化简前的程序具有相同的count值。
(3) 程序执行结束时的count值是多少？
(4) 使用执行次数的方法计算这个程序的程序步数，画出程序步数统计表。
第2章线性表
一 选择题
1．下述哪一条是顺序存储结构的优点？( )
A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示
2．下面关于线性表的叙述中，错误的是哪一个？( )
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
3．线性表是具有n个( )的有限序列（n>0）。
A．表元素 B．字符 C．数据元素 D．数据项 E．信息项
4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表
6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。
A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表
7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用( )存储方式最节省运算时间。
A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表
8. 静态链表中指针表示的是( )
A． 内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址
9. 链表不具有的特点是( )
A．插入、删除不需要移动元素 B．可随机访问任一元素
C．不必事先估计存储空间 D．所需空间与线性长度成正比
10. 下面的叙述不正确的是( )
A．线性表在链式存储时，查找第i个元素的时间同i的值成正比
B. 线性表在链式存储时，查找第i个元素的时间同i的值无关
C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比
D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关
12.(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。
(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。
(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。
以上错误的是( )
A．（1），（2） B．（1） C．（1），（2）,(3) D.（2）
13.
若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。
A. O(0) B. O(1) C. O(n) D. O(n2)
14. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为( )
A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)
15．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为( )
A．O(i) B．O（1） C．O（n） D．O（i-1）
16．非空的循环单链表head的尾结点p↑满足( )
A．p↑.link=head B．p↑.link=NIL C．p=NIL D．p= head
17．循环链表H的尾结点P的特点是( )
A．P^.NEXT:=H B．P^.NEXT:= H^.NEXT C．P:=H D.P:=H^.NEXT
18．在一个以 h 为头的单循环链中，p 指针指向链尾的条件是( )
A. p＾.next=h B. p＾.next=NIL C. p＾.next.＾next=h D. p＾.data=-1
19．完成在双循环链表结点p之后插入s的操作是( )
A． p^.next:=s ; s^.priou:=p; p^.next^.priou:=s ;
s^.next:=p^.next;
B． p^.next^.priou:=s; p^.next:=s; s^.priou:=p;
s^.next:=p^.next;
C． s^.priou:=p; s^.next:=p^.next; p^.next:=s;
p^.next^.priou:=s;
D． s^.priou:=p; s^.next:=p^.next; p^.next^.priou:=s ;
p^.next:=s;
20．在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是( )
注:双向链表的结点结构为(llink,data,rlink)。供选择的答案：
A． p↑.llink：=q； q↑.rlink：=p； p↑.llink↑.rlink：=q； q↑.llink：=q；
B． p↑.llink：=q； p↑.llink↑.rlink：=q ； q↑.rlink：= p；
q↑.llink:=p↑.llink；
C． q↑.rlink：=p； q↑.llink：=p↑.llink； p↑.llink↑.rlink：=q;
p↑.llink：=q;
D． q↑.llink:=p↑.llink；q↑.rlink:=p；
p↑.llink：=q；p↑.llink：=q；（编者按：原题如此）
21．在非空双向循环链表中q所指的结点前插入一个由p所指的链结点的过程依次为:
rlink(p) ← q; llink(p) ← llink(q); llink(q) ← p; ( )
A．rlink(q) ← p B．rlink(llink(q)) ← p C．rlink(llink(p)) ← p
D．rlink(rlink(p)) ← p
22．
双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为(
)
A. p＾.llink:=q; q＾.rlink:=p; p＾.llink＾.rlink:=q;
q^.llink:=p^.llink;
B. q＾.llink:=p^.llink; p＾.llink^.rlink:=q; q＾.rlink:=p;
p^.llink:=q^.rlink;
C. q^.rlink:=p; p^.rlink:=q; p^.llink^.rlink:=q; q^.rlink:=p;
D. p^.llink^.rlink:=q; q^.rlink:=p; q^.llink:=p^.llink;
p^.llink:=q;
23．在双向链表指针p的结点前插入一个指针q的结点操作是( )
A.
p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；
B.
p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;
C.
q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;
D.
q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;
24．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：( )
A．p->next=s;s->next=p->next; B．
s->next=p->next;p->next=s;
C．p->next=s;p->next=s->next; D．
p->next=s->next;p->next=s;
25．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是( )
A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL
26. 在双向链表存储结构中，删除p所指的结点时须修改指针( )
A． (p^.llink)^.rlink:=p^.rlink (p^.rlink)^.llink:=p^.llink;
B． p^.llink:=(p^.llink)^.llink (p^.llink)^.rlink:=p;
C． (p^.rlink)^.llink:=p p^.rlink:=(p^.rlink)^.rlink
D． p^.rlink:=(p^.llink)^.llink p^.llink:=(p^.rlink)^.rlink;
27.
双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，现要求删去p所指结点，则正确的删除是(
)（链中结点数大于2，p不是第一个结点）
A．p^.llink^.rlink:=p^.llink; p^.llink^.rlink:=p^.rlink;
dispose(p);
B．dispose(p); p^.llink^.rlink:=p^.llink;
p^.llink^,rlink:=p^.rlink;
C．p^.llink^.rlink:=p^.llink; dispose(p);
p^.llink^.rlink:=p^.rlink;
D．以上A，B，C都不对。
二、判断题
1. 链表中的头结点仅起到标识的作用。( )
2. 顺序存储结构的主要缺点是不利于插入或删除操作。( )
3．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( )
4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( )
5. 对任何数据结构链式存储结构一定优于顺序存储结构。( )
6．顺序存储方式只能用于存储线性结构。( )
7．集合与线性表的区别在于是否按关键字排序。( )
8. 所谓静态链表就是一直不发生变化的链表。( )
9. 线性表的特点是每个元素都有一个前驱和一个后继。( )
10. 取线性表的第i个元素的时间同i的大小有关. ( )
11. 循环链表不是线性表.( )
12. 线性表只能用顺序存储结构实现。( )
13. 线性表就是顺序存储的表。( )
14．为了很方便的插入和删除数据，可以使用双向链表存放数据。( )
15. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )
16. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 ( )
三、填空题
1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。
2．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。
3．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点
, 若将结点y插入结点x之后，则需要执行以下语句:_______；______;
4．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。
5．在单链表中设置头结点的作用是________。
6．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。
7．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成________和_______；而又根据指针的连接方式，链表又可分成________和________。
8．
在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_______、_______、_______、________。
9. 在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句：
s^ .next:=p； s^ .prior:= ________；p^ .prior:=s；________:=s；
10．链接存储的特点是利用________来表示数据元素之间的逻辑关系。
11.顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。
12. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ______个，单链表为_______个。
13. 循环单链表的最大优点是：________。
14. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：_______
15. 带头结点的双循环链表L中只有一个元素结点的条件是：________
16. 在单链表L中，指针p所指结点有后继结点的条件是：________
17.带头结点的双循环链表L为空表的条件是：________
18. 在单链表p结点之后插入s结点的操作是：_______
19. 请在下列算法的横线上填入适当的语句。
FUNCTION inclusion(ha,hb:linklisttp):boolean;
{以ha和hb为头指针的单链表分别表示有序表A和B，本算法判别表A是否包含在表B内，若是，则返回“true”，否则返回“false”}
BEGIN
pa:=ha^.next; pb:=hb^.next;
（1）;
WHILE
（2）DO
IF pa^.data=pb^.data THEN
（3） ELSE
（4）;
（5）
END;
20．完善算法：已知单链表结点类型为：
TYPE ptr=^node；
node=RECORD
data：integer； next：ptr
END；
过程create建立以head为头指针的单链表。
PROCEDURE create (
(1) )；
VAR p,q：ptr； k：integer；
BEGIN
new（head）； q:=head；read（k）；
WHILE k>0 DO
BEGIN
(2);
(3);
(4);
(5);
read（k）
END
q^.next：=NIL
END;
21. 已给如下关于单链表的类型说明：
TYPE
list=^node;
node=RECORD
data: integer; next: list;
END;
以下程序采用链表合并的方法，将两个已排序的单链表合并成一个链表而不改变其排序性（升序），这里两链表的头指针分别为p和q.
PROCEDURE mergelink(VAR p,q:list):
VAR h,r: list;
BEGIN
（1）
h^.next:= NIL; r:=h;
WHILE((p<>NIL) AND (q<>NIL)) DO
IF (p^.data<=q^.data)
THEN BEGIN
（2）； r:=p; p:=p^.next； END
ELSE BEGIN
（3）； r:=q; q:=q^.next; END;
IF (p=NIL) THEN r^.next:=q;
（4）；
p:=h^.next; dispose(h);
END;
22．假设链表p和链表q中的结点值都是整数,且按结点值的递增次序链接起来的带表头结点的环形链表。各链表的表头结点的值为max,且链表中其他结点的值都小于max，在程序中取max为9999。在各个链表中，每个结点的值各不相同，但链表p和链表q可能有值相同的结点（表头结点除外）。下面的程序将链表q合并到链表p中，使得合并后的链表是按结点值递增次序链接起来的带表头结点的环形链表，且链表中各个结点的值各不相同。请在划线处填上适当内容，每个框只填一个语句或一个表达式，链表的结点类型如下
TYPE nodeptr=^nodetype；
nodetype=RECORD
data：integer； link：nodeptr;
END；
CONST max=9999;
PROCEDURE merge(VAR p:nodeptr;q:nodeptr);
VAR r,s: nodeptr;
BEGIN
r:=p;
WHILE
(A)___ DO
BEGIN
WHILE r^.link^.data<q^.link^.data DO
(B)___;
IF r^.link^.data>q^.link^.data
THEN BEGIN s:=
(C)_; (D)_:=s^.link;
s^.link:=
(E)_; (F)_ _:=s;
(G)_; END
ELSE BEGIN
(H)__; s:=q^.link;
(I)__; dispose(s)
END
END;
dispose(q)
END;
23．PROC ins__linklist(la:linkisttp; i:integer; b:elemtp);
{la为指向带头结点的单链表的头指针，本算法在表中第i个元素之前插入元素b}
p:=
(1) ; j:=
(2) ;{指针初始化，j为计数器}
WHILE (p<>NIL) AND (
(3) ) DO [p:=
(4) ;
j:=j+1；]
{寻找第 i-1 个结点
IF (p=NIL) OR
((5) )
THEN error (‘No this position’)
ELSE [new(s) ; s↑.data:=b; s↑.next:=p↑.next; p↑.next:=s;]
ENDP;{ins-linklist}
24. 已知双链表中结点的类型定义为：
TYPE dpointer=^list;
list=RECORD
data:integer; left,right:dpointer;
END;
如下过程将在双链表第i个结点（i>=0）之后插入一个元素为x的结点，请在答案栏给出题目中______处应填入的语句或表达式，使之可以实现上述功能。
PROCEDURE insert(VAR head:dpointer;i,x:integer);
VAR s,p:dpointer; j: integer;
BEGIN
new(s); s^.data:=x;
IF(i=0)THEN BEGIN s^.right:=head;
(1)___ head:=s
END{如果i=0,则将s结点插入到表头后返回}
ELSE BEGIN p:=head;
(2)_______；{在双链表中查找第i个结点,由p所指向}
WHILE ((p<>NIL) AND (j<i)) DO BEGIN j:=j+1;
(3) _
END;
IF p<>NIL THEN
IF （p^.right=NIL）
THEN BEGIN p^.right:=s; s^.right:=NIL;
(4) __END
ELSE BEGIN s^.right:=p^.right;
(5) _;p^.right:=s;
(6)
END
ELSE writeln(‘can not find node!’)
END
END;
25．阅读以下算法，填充空格，使其成为完整的算法。其功能是在一个非递减的顺序存储线性表中，删除所有值相等的多余元素。
CONST maxlen=30
TYPE sqlisttp=RECORD
elem:ARRAY[1..maxlen] OF integer;
last:0..maxlen
END;
PROC exam21(VAR L:sqlisttp);
j:=1;i:=2;
WHILE
(1) DO
[ IF L.elem[i]<>L.elem[j] THEN [
(2);
(3)];
i:=i+1 ]
(4);
ENDP;
四．问答及应用题
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停留在链表最右边的结点上。
(2) 编写一个算法，从任一给定的位置(
pr,
p)开始，将指针
p左移1个结点。如果
pr移出链表，则将
pr置为
NULL，并让
p停留在链表最左边的结点上。要求讨论
p最初为
NULL的情形并能有效处理。
6
试写出用单链表表示的字符串类及字符串结点类的定义，并依次实现它的构造函数、以及计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等7个成员函数。要求每个字符串结点中只存放一个字符。
7 如果用循环链表表示一元多项式，试编写一个函数Polynomial
::
Calc(x)，计算多项式在x处的值。
8 设
a和
b是两个用带有表头结点的循环链表表示的多项式。试编写一个算法，计算这两个多项式的乘积c =
a*b，要求计算后多项式a与b保持原状。如果这两个多项式的项数分别为n与m,
试说明该算法的执行时间为O(nm2)或O(n2m)。但若a和b是稠密的, 即其很少有系数为零的项,
那么试说明该乘积算法的时间代价为O(nm)。
9 计算多项式
Pn (
x) =
a0
xn +
a1
xn-1 +
a2
xn-2 + …… +
an-1
x +
an的值，通常使用的方法是一种嵌套的方法。它可以描述为如下的迭代形式：
b0 =
a0 ,
bi+1 =
x *
bi +
ai+1,
i = 0, 1,
…,
n-1。若设
bn =
pn （
x）.
则问题可以写为如下形式：
Pn (
x) =
x *
Pn-1
(
x) +
an ，此处，
Pn-1 (
x) =
a0
xn-1 +
a1
xn-2 + …… +
an-2
x +
an-1，这是问题的递归形式。试编写一个递归函数，计算这样的多项式的值。
10
试设计一个实现下述要求的Locate运算的函数。设有一个带表头结点的双向链表L，每个结点有4个数据成员：指向前驱结点的指针
prior、指向后继结点的指针
next、存放数据的成员
data和访问频度
freq。所有结点的
freq初始时都为0。每当在链表上进行一次Locate
(x)操作时，令元素值为
x的结点的访问频度
freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。
11 利用双向循环链表的操作改写 2题，解决约瑟夫(Josephus)问题。
第3章栈与队列
一、选择题
1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（
）。
A. 13 B. 33 C. 18 D. 40
2. 有一个二维数组A[1:6，0:7]
每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（①）个字节。假设存储数组元素A[1，0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（②）。若按行存储，则A[2，4]的第一个字节的地址是（③）。若按列存储，则A[5，7]的第一个字节的地址是（④）。就一般情况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。供选择的答案：
①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120
G. 156 H. 234 I. 276 J. 282 K. 283 L. 288
⑤： A．行与列的上界相同 B. 行与列的下界相同
C. 行与列的上、下界都相同 D. 行的元素个数与列的元素个数相同
3. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1
到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。
A. BA+141 B. BA+180 C. BA+222 D. BA+225
4.
假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。
A. 808 B. 818 C. 1010 D. 1020
5.
数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是(
)。
A. 1175 B. 1180 C. 1205 D. 1210
6.
有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素A[0,1]的第一个字节的地址是0，存储数组A的最后一个元素的第一个字节的地址是（
① ）。若按行存储，则A[3,5]和 A[5,3]的第一个字节的地址是（ ② ） 和（ ③
）。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址是（ ④ ）和（ ⑤ ）。
①-⑤:A.28 B.44 C.76 D.92 E.108 F.116 G.132 H.176 I.184 J.188
7.
将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（
）。供选择的答案：
A. 198 B. 195 C. 197
8.
二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中（）内的正确答案。
（1）存放A至少需要（ ）个字节；
（2）A的第8列和第5行共占（ ）个字节；
（3）若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（）的起始地址一致。
供选择的答案：
（1）A. 90 B. 180 C. 240 D. 270 E. 540
（2）A. 108 B. 114 C. 54 D. 60 E. 150
（3）A. A[8,5] B. A[3,10] C. A[5,8] D. A[0,9]
9.
二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（
）的起始地址相同。设每个字符占一个字节。
A. A[8,5] B. A[3,10] C. A[5,8] D. A[0,9]
10.
若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i<j）的位置k的关系为(
)。
A. i*(i-1)/2+j B. j*(j-1)/2+i C. i*(i+1)/2+j D. j*(j+1)/2+i
11.
设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为(
)。
A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-1
12.
A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。
A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+1
13. 设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1..
m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。
A.（i-1）*n+j B.（i-1）*n+j-1 C. i*（j-1） D. j*m+i-1
14. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（
）。
A. 60 B. 66 C. 18000 D. 33
15. 数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）。
A. 55 B. 45 C. 36 D. 16
16. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。
A. j=r[j].next B. j=j+1 C. j=j->next D. j=r[j]-> next
17. 对稀疏矩阵进行压缩存储目的是（ ）。
A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度
二、判断题
1. 数组不适合作为任何二叉树的存储结构。（ ）
2. 从逻辑结构上看，n维数组的每个元素均属于n个向量。（）
3. 稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）
4. 数组是同类型值的集合。（ ）
5. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ ）
6. 一个稀疏矩阵Am*n采用三元组形式表示，
若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（）
7. 二维以上的数组其实是一种特殊的广义表。（ ）
三、 填空题
1. 数组的存储结构采用_______存储方式。
2. 设二维数组A[-20..30,-30..20], 每个元素占有4 个存储单元, 存储起始地址为200.如按行优先顺序存储,则元素
A[25,18]的存储地址为
__（1）_；如按列优先顺序存储,则元素A[-18,-25]的存储地址为
__（2）_。
3.
设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为
_（1）_;若以列序为主序顺序存储，则元素a[45,68]的存储地址为
_（2）_。
4.
将整型数组A[1..8，1..8]按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[7，3]的地址是：_______。
5.
二维数组a[4][5][6]（下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]的地址是____。(设a[0][0][0]的地址是1000,数据以行为主方式存储)
6.
设有二维数组A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为_______。
7.
已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为_______。
8.
已知二维数组A[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是：_______。
9. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j]
(1
≤i
≤n,i-2
≤j
≤i+2),B中的第8个元素是A
中的第
_（1）_行，第
_（2）_列的元素。
10.
设数组A[0..8,1..10],数组中任一元素A[i,j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么
（l） 存放该数组至少需要的单元数是_______;
（2） 存放数组的第8列的所有元素至少需要的单元数是_______;
（3） 数组按列存储时，元素A[5,8]的起始地址是_______。
11．设n行n列的下三角矩阵A已压缩到一维数组B[1..n*（n+1）/2]中，若按行为主序存储，则A[i,j]对应的B中存储位置为_______。
12.
n阶对称矩阵a满足a[i][j]=a[j][i],i,j=1..n,，用一维数组t存储时，t的长度为
__(1)______，当i=j，a[i][j]=t[(2)],i>j,a[i][j]=t[(3)],i<j,a[i][j]=t[(4)]。
13．己知三对角矩阵A
的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A[7,8]的地址为______。
14. 设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a11=1），则a85 的地址为_______。
15. 所谓稀疏矩阵指的是_______。
16. 对矩阵压缩是为了_______。
17. 上三角矩阵压缩的下标对应关系为：_______。
18.
假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素A9,9在B中的存储位置k=_______。（注：矩阵元素下标从1开始）
19．设下三角矩阵A=
如果按行序为主序将下三角元素Ai j (i,j)存储在一个一维数组B[ 1..n(n+1)/2]中，对任一个三角矩阵元素Aij
,它在数组B中的下标为_______。
35.
已知a数组元素共5个，依次为12，10，5，3，1；b数组元素共4个，依次为4,6,8,15，则执行如下所示的过程语句sort后得到c数组各元素依次为15,12,10,8,6,5,4,3,1；数组a,b,c的长度分别为l=5,m=4,n=9请在程序中方框内填入正确的成分，完成上述要求。
PROCEDURE sort;
VAR i, j, k, x: integer; d: ARRAY[1..m] OF integer;
BEGIN
FOR i:=1 TO m DO d[i]:=
(1) ;
i:=1; j:=1; k:=1;
WHILE (i<=l) AND (j<=m) DO
BEGIN
IF a[i]>d[j] THEN BEGIN
(2) ;
(3) _END
ELSE BEGIN
(4)__;
(5) __END;
c[k]:=x;
(6)
END;
WHILE
(7) _DO
BEGIN c[k]:=a[i]; k:=k+1; i:=i+1；END;
WHILE
(8) _DO
BEGIN c[k]:=d[j]; k:=k+1; j:=j+1；END;
END. {sort}
36.
下列程序段search(a,n,k)在数组a的前n(n>=1)个元素中找出第k(1<=k<=n)小的值。这里假设数组a中各元素的值都不相同。
#define MAXN 100
int a[MAXN],n,k;
int search_c(int a[], int n, int k)
{int low, high, i, j, m, t;
k--,;low=0 ;high=n-1;
do {i=low; j=high ; t=a[low];
do{while (i<j && t<a[j]) j--;
if (i<j) a[i++]=a[j];
while (i<j && t>=a[i]) i++
if (i<j) a[j--]=a[i];
} while (i<j);
a[i]=t;
if
(1) ;
if (i<k) low=
(2) ; else high=
(3) ;
}while
(4) _;
return(a[k]);
}
37.
完善下列程序，每小题在PASCAL语言（a）和C语言（b）中任选一题。下面是一个将广义表逆置的过程。例如原来广义表为（（a,b）,c,（d,e）），经逆置后为：（（e,d）,c,（b,a））。
（a）算法的PASCAL语言过程描述（编者略）：（b）算法的C语言过程描述：
typedef struct glistnode
{int tag;
struct glistnode *next;
union{char data;
struct{struct glistnode *hp,*tp;}ptr;
}val;
}*glist,gnode;
glist reverse(p)
glist p;
{glist q,h,t,s;
if(p==NULL) q=NULL;
else
{if
(1) { q=(glist)malloc(sizeof(gnode)); q->tag=0;
q->val.data=p->val.data; }
else {
(2)
if
(3)
{t=reverse(p->val.ptr.tp); s=t;
while(s->val.ptr.tp!=NULL) s=s->val.ptr.tp;
s->val.ptr.tp=(glist)malloc(sizeof(gnode));
s=s->val.ptr.tp;s->tag=1;s->val.ptr.tp=NULL;
s->val.ptr.hp=h;
(4) __ }
else {q=(glist)malloc(sizeof(gnode));q->tag=1;
q->val.ptr.tp=NULL;
(5) ; }
}
}
return(q);
}
38.
完善下列程序，每小题在PASCAL语言（a）和C语言（b）中任选一题。下面的程序将数列1,2,3,…,n*n,依次按蛇型方式存放在二维数组A[1..n,1..n]中。即
(示意圖编者略)。
（a）算法的PASCAL 语言程序描述（编者略）：（b）算法的C语言程序描述：
#define NMAX 10
#include “stdio.h”
main()
{ int i,j,n,k,p,q,m;
int a [NMAX][NMAX];
scanf(“%d”,&n);
m=1;
for(k=1；
(1) ；k++)
{if（k<n） q=k； else
(2) __;
for(p=1;p<=q;p++)
{if
(3) {i=q-p+1；j=p；}
else{i=p；j=q-p+1；}
if
(4) {i=i+n-q；j=j+n-q；}
a[i][j]=m；
(5) _;
}
for（i=1；i<=n;i++）
{ for（j=1；j<=n；j++）
printf（“M”,a[i][j]）;printf(“”);
}
}
}
39.
约瑟夫环问题：设有n个人围坐一圈，并按顺时针方向1—n编号。从第s个人开始进行报数，报数到第m个人，此人出圈，再从他的下一个人重新开始从1到m的报数进行下去
，直到所有的人都出圈为止。
PROCEDURE Josef (A:ARRAY [1..n] OF integer; s,m:integer);
BEGIN
FOR i:= 1 TO n DO A[i]:=i;
sl:=s;
FOR i:=n DOWNTO 2 DO
BEGIN sl:=
(1) __；//计算出圈人s1
IF sl=0 THEN
(2) _；
w:=A[sl]; //A[s1]出圈
FOR j:=
(3) __ DO A[j]:=A[j+1];
A[i]:=w;
END;
write('出圈序列为：’)；//输出出圈序列
FOR i :=n DOWNTO 1 DO write(A[i]); writeln ；
END;
40.
设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，...，Wn。问能否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。设布尔函数Knap(S，n)表示背包问题的解，Wi(i=1,2,...，n)均为正整数，并已顺序存储地在数组W中。请在下列算法的下划线处填空，使其正确求解背包问题。
Knap(S，n)
若S=0
则Knap←true
否则若（S<0）或(S>0且n<1)
则Knap←false
否则若Knap
(1) , _=true
则print(W[n])；Knap ←true
否则 Knap←Knap
(2) _ , _
四．问答及应用
1
设
n个人围坐在一个圆桌周围，现在从第
s个人开始报数，数到第
m个人，让他出局；然后从出局的下一个人重新开始报数，数到第
m个人，再让他出局，……，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的
n,
s和
m，求出这
n个人的出局序列。请以
n = 9,
s = 1,
m = 5为例，人工模拟Josephus的求解过程以求得问题的解。
2 试编写一个求解Josephus问题的函数。用整数序列1, 2, 3, ……,
n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。然后使用
n = 9,
s = 1,
m = 5，以及
n = 9,
s = 1,
m =
0，或者
n = 9,
s = 1,
m =
10作为输入数据，检查你的程序的正确性和健壮性。
3 设有一个线性表（
e0,
e1, …,
en-2,
en-1）存放在一个一维数组
A[
arraySize]中的前
n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前
n个原址内容置换为（
en-1,
en-2, …,
e1,
e0）。
4 假定数组
A[
arraySize]中有多个零元素, 试写出一个函数, 将
A
中所有的非零元素依次移到数组
A的前端
A[
i]（0￡
i ￡
arraySize）。
5 顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有127个元素的顺序表进行插入, 平均需要移动多少个元素
删除一个元素, 又平均需要移动多少个元素
6
若矩阵
Am′
n中的某一元素A[i][j]是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵的一个鞍点。假设以二维数组存放矩阵，试编写一个函数，确定鞍点在数组中的位置（若鞍点存在时），并分析该函数的时间复杂度。
7
设有一个二维数组
A[
m][
n]，假设
A[0][0]存放位置在644（10），
A[2][2]存放位置在676（10），每个元素占一个空间，问
A[3][3]（10）存放在什么位置？脚注（10）表示用10进制表示。
8 利用顺序表的操作，实现以下的函数。
(1)
从顺序表中删除具有最小值的元素并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。
(2) 从顺序表中删除第i个元素并由函数返回被删元素的值。如果i不合理或顺序表为空则显示出错信息并退出运行。
(3) 向顺序表中第i个位置插入一个新的元素x。如果i不合理则显示出错信息并退出运行。
(4) 从顺序表中删除具有给定值x的所有元素。
(5)
从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素，如果s或t不合理或顺序表为空则显示出错信息并退出运行。
(6)
从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素，如果s或t不合理或顺序表为空则显示出错信息并退出运行。
(7) 将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表。
(8) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。
9
设有一个
n′
n的对称矩阵
A，如图（a）所示。为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组
B中，如图（b）和图（c）所示。并称之为对称矩阵
A的压缩存储方式。试问：
(1) 存放对称矩阵
A上三角部分或下三角部分的一维数组
B有多少元素？
(2)
若在一维数组
B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素
aij在只存上三角部分的情形下（图(b)）应存于一维数组的什么下标位置？给出计算公式。
(3)
若在一维数组
B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素
aij在只存下三角部分的情形下（图(c)）应存于一维数组的什么下标位置？给出计算公式。
10
设
A和
B均为下三角矩阵，每一个都有
n行。因此在下三角区域中各有
n（
n+1）/2个元素。另设有一个二维数组
C，它有
n行
n+1列。试设计一个方案，将两个矩阵
A和
B中的下三角区域元素存放于同一个
C中。要求将
A的下三角区域中的元素存放于
C的下三角区域中，
B的下三角区域中的元素转置后存放于
C的上三角区域中。并给出计算
A的矩阵元素
aij和
B的矩阵元素
bij在
C中的存放位置下标的公式。
11
在实际应用中经常遇到的稀疏矩阵是三对角矩阵，如右图所示。在该矩阵中除主对角线及在主对角线上下最临近的两条对角线上的元素外，所有其它元素均为0。现在要将三对角矩阵
A中三条对角线上的元素按行存放在一维数组
B中，且
a11存放于
B[0]。试给出计算
A在三条对角线上的元素
aij
（1￡
i ￡
n,
i-1 ￡
j ￡
i+1）在一维数组
B中的存放位置的计算公式。
12
设带状矩阵是
n′
n阶的方阵，其中所有的非零元素都在由主对角线及主对角线上下各
b条对角线构成的带状区域内，其它都为零元素。试问：
(1) 该带状矩阵中有多少个非零元素？
(2)
若用一个一维数组
B按行顺序存放各行的非零元素，且设
a11存放在
B[0]中，请给
出一个公式，计算任一非零元素
aij在一维数组
B中的存放位置。
13
稀疏矩阵的三元组表可以用带行指针数组的二元组表代替。稀疏矩阵有多少行，在行指针数组中就有多少个元素：第
i个元素的数组下标
i代表矩阵的第
i行，元素的内容即为稀疏矩阵第
i行的第一个非零元素在二元组表中的存放位置。二元组表中每个二元组只记录非零元素的列号和元素值，且各二元组按行号递增的顺序排列。试对右图所示的稀疏矩阵，分别建立它的三元组表和带行指针数组的二元组表。
14 字符串的替换操作replace ( String
& s, String
& t,
String
& v)
是指：若t是s的子串，则用串v替换串t在串s中的所有出现；若t不是s的子串，则串s不变。例如，若串s为“aabbabcbaabaaacbab”，串t为“bab”，串v为“abdc”，则执行replace操作后，串s中的结果为“aababdccbaabaaacabdc”。试利用字符串的基本运算实现这个替换操作。
15 编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。
