严蔚敏++数据结构习题集答案文档格式.docx

1、6 循环链表的主要优点是（ ） 。（A）不在需要头指针了（B）已知某个结点的位置后，能够容易找到他的直接前趋（C）在进行插入、删除运算时，能更好的保证链表不断开（D）从表中的任意结点出发都能扫描到整个链表7 下面关于线性表的叙述错误的是（ ）。（A） 线性表采用顺序存储，必须占用一片地址连续的单元；（B） 线性表采用顺序存储，便于进行插入和删除操作；（C） 线性表采用链式存储，不必占用一片地址连续的单元；（D） 线性表采用链式存储，不便于进行插入和删除操作；8 单链表中，增加一个头结点的目的是为了（）。（A） 使单链表至少有一个结点 （B）标识表结点中首结点的位置（C）方便运算的实现 （D）

2、说明单链表是线性表的链式存储9 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。（A） 单链表 （B） 仅有头指针的单循环链表 （C） 双链表 （D） 仅有尾指针的单循环链表10 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省运算时间（ ）。（A） 单链表 （B） 顺序表 （C） 双链表 （D） 单循环链表三 填空题1带头结点的单链表H为空的条件是_。1 非空单循环链表L中*p是尾结点的条件是_。3在一个单链表中p所指结点之后插入一个由指针f所指结点，应执行s-next=_;和p-next

3、=_的操作。4在一个单链表中p所指结点之前插入一个由指针f所指结点，可执行以下操作：s-p-next=s;t=p-data;data=_;5在顺序表中做插入操作时首先检查_。四 算法设计题1 设线性表存放在向量Aarrsize的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。2 已知一顺序表A，其元素值非递减有序排列，编写一个函数删除顺序表中多余的值相同的元素。3 编写一个函数，从一给定的顺序表A中删除值在xy（x=y）之间的所有元素，要求以较高的效率来实现。提示：可以先将顺序表中所有值在xy之间的元素置成一个特殊

4、的值，并不立即删除它们，然后从最后向前依次扫描，发现具有特殊值的元素后，移动其后面的元素将其删除掉。4 线性表中有n个元素，每个元素是一个字符，现存于向量Rn中，试写一算法，使R中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素移动次数最小。（研54）5 线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换。即将线性表（a1, a2, , am, b1, b2, , bn） 改变为：（b1, b2, , bn , a1, a2, , am）。6 已知带头结点的单链表L中的结点是按整数值递增排列的，试写一算法，将值为x

5、的结点插入到表L中，使得L仍然有序。7 假设有两个已排序的单链表A和B，编写一个函数将他们合并成一个链表C而不改变其排序性。8 假设长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点的指针，编写一个函数删除该结点的前趋结点。9 已知两个单链表A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和B的交集C，要求C同样以元素递增的单链表形式存储。10 设有一个双向链表，每个结点中除有prior、data和next域外，还有一个访问频度freq域，在链表被起用之前，该域其值初始化为零。每当在链表进行一次Locata（L,x）运算后，令值为x的结点中的freq域增1，并调

6、整表中结点的次序，使其按访问频度的递减序列排列，以便使频繁访问的结点总是靠近表头。试写一个算法满足上述要求的Locata（L,x）算法。五 上机实习题目1 Josephu 问题Josephu 问题为：设编号为1，2， n的n个人围坐一圈，约定编号为k（1=k0）个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。源程序代码：（在Tubr

7、o C 2.0测试通过）#include alloc.hstruct node int number; /* 人的序号 */ int cipher; /* 密码 */ struct node *next; /* 指向下一个节点的指针 */;struct node *CreatList（int num） /* 建立循环链表 */ int i; struct node *ptr1,*head; if（ptr1=（struct node *）malloc（sizeof（struct node）=NULL） perror（malloc）; return ptr1; head=ptr1; ptr1-ne

8、xt=head; for（i=1;inext=（struct node *）malloc（sizeof（struct node）=NULL） return head; ptr1=ptr1-next;main（） int i,n=30,m; /* 人数n为30个 */ struct node *head,*ptr; randomize（）; head=CreatList（n）;=30; head-number=i;cipher=rand（）; head=head- m=rand（）; /* m取随机数 */ i=0; /* 因为我没办法删除head指向的节点，只会删除head的下一节点，所以只能

9、从0数起。*/ while（head-next!=head） /* 当剩下最后一个人时，退出循环 */ if（i=m） ptr=head- /* ptr记录数到m的那个人的位置 */ printf（number:%dn,ptr-number）;cipher:cipher）; m=ptr-cipher; /* 让m等于数到m的人的密码 */next=ptr- /* 让ptr从链表中脱节，将前后两个节点连接起来 */ head=hea/d- /* head移向后一个节点 */ free（ptr）; /* 释放ptr指向的内存 */ /* 将i重新置为0，从0再开始数 */ else i+;,hea

10、d- free（head）; /* 让最后一个人也出列 */第三章 习题一、 基本题1填空：线性表、栈和队列都是_结构，可以在线性表的_位置插入和删除元素，对于栈只能在_位置插入和删除元素，对于队只能在_位置插入和_位置删除元素。2. 栈和队列数据结构的特点，什么情况下用到栈，什么情况下用到队列？3设有编号为1，2，3，4的四辆车，顺序进入一个栈式结构的站台，试写出这四辆车开出车站的所有可能的顺序（每辆车可能入站，可能不入站，时间也可能不等）。4试证明：若借助栈由输入序列1，2， ，n得到输出序列为p1p2pn （它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着ijk，使得

11、pjpk pi 。二、 设计算法题1 假设称正读和反读都相同的字符序列为“回文”，例如，“abcddcba”、 “qwerewq”是回文，“ashgash”不是回文。是写一个算法判断读入的一个以为结束符的字符序列是否为回文。2 设以数组sem存放循环队列的元素，同时设变量rear 和front分别作为队头队尾指针，且队头指针指向队头前一个位置，写出这样设计的循环队列入队出队的算法。3 假设以数组sem存放循环队列的元素，同时设变量rear 和num分别作为队尾指针和队中元素个数记录，试给出判别此循环队列的队满条件，并写出相应入队和出队的算法。4 假设以带头结点的循环链表表示一个队列，并且只设一

12、个队尾指针指向尾元素结点（注意不设头指针），试写出相应的置空队、入队、出队的算法。5 设计一个算法判别一个算术表达式的圆括号是否正确配对。6 写一个算法，借助于栈将一个单链表置逆。7两个栈共享向量空间vm，它们的栈底分别设在向量的两端，每个元素占一个分量，试写出两个栈公用的栈操作算法：push（i,x）、pop（i）和top（i），i=0和1 ,用以指示栈号。三、 实验题目1 背包问题的求解：假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + + wn=T，要求找出所有满足上述条件的解。例如：当T=

13、10，各件物品的体积1，8，4，3，5，2时，可找到下列4组解：（1，4，3，2） （1，4，5） （8，2） （3，5，2）。可利用回溯法的设计思想来解决背包问题。首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直至求得满足条件的解，或者无解。由于回溯求解的规则规则是“后进先出”因此自然要用到栈。2

14、模拟停车厂管理的问题。设停车厂只有一个可停放几辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达的先后顺序依次排列，若车场内已停满几辆汽车，则后来的汽车只能在门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆车即可进入；当停车场内某辆车要离开时，由于停车场是狭长的通道，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门后，为它让路的车辆再按原次序进入车场。在这里假设汽车不能从便道上开走。试设计一个停车场管理程序。第四章习题算法设计题1利用C的库函数strlen,strcpy和strcat写一个算法void StrInsert（char *S,char *T

15、,int t） ，将串T插入到S的第i个位置上。若i大于S的长度，则插入不执行。2利用C的库函数strlen,strcpy（或strncpy）写一个算法void StrDelete（char *S,int t,int m） ，删除串S中从位置I开始的连续的m个字符。若istrlen（S），则没有字符被删除；若i+mstrlen（S），则将S中从位置i开始直至末尾的字符均被删去。3采用顺序结构存储串，编写一个函数，求串和串的一个最长的公共子串。4采用顺序存储结构存储串，编写一个函数计算一个子串在一个字符串中出现的次数，如果该子串不出现则为0。第五章习题一、单项选择题1. 二维数组M的成员是6个字

16、符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要（1）个字节；M的第8列和第5行共占（2）个字节；若M按行优先方式存储，元素M85的起始地址与当M按列优先方式存储时的（3）元素的起始地址一致。（） （1） A.90 B.180 C.240 D.540 （2） A.108 B.114 C.54 D.60 （3） A.M85 B.M310 C.M58 D.M092. 二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M35的起始地址与M按列存储时元素（1）的起始地址相

17、同。 A.m24 B.M34 C.M35 D.M44 3. 数组A中，每个元素A的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（1），若该数组按行存放时，元素A85的起始地址是（2），若该数组按列存放时，元素A85的起始地址是（）。 （1） A. 80 B.100 C.240 D.270 （2） A.SA+141 B.SA+144 C.SA+222 D.SA+225（3） A.SA+141 B.SA+180 C.SA+222 D.SA+225 4. 稀疏矩阵一般的压缩存储方法有两种，即（） A.二维数组和三维数组 B.

18、 三元组和散列 C.三元组和十字链表 D. 散列和十字链表5.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（） A.正确 B.错误6.假设按行优先存储整数数组A9358时，第一个元素的字节地址时，每个整数占个字节。问下列元素的存储地址是什么。（1） a0000 （2）a1111 （3）a3125 （4）a82477.设有三对角矩阵Ann，将其三条对角线上的元素存于数组B3n中，使得元素Buv=aij，试推倒出从（i,j）到 （u,v）的下标变换公式。8.假设一个准对角矩阵：a11 a12a21 a22a33 a34a43 a44 .

19、 aij a2m-1,2m-1 a2m-1,2m a2m,2m-1 a2m,2m 按以下方式存储于一维数组B4m中:1 2 3 4 5 6 k 4m-1 4mA11a12a21a22a33a34a43aija2m-1,2ma2m,2m-1a2m,2m写出由一对下标（i,j）求k的转换公式。 9.画出下列广义表的存储结构式意图。（1） A=（a,b,c）,d,（a,b,c）（2） B=（a,（b,（c,d）,e）,f）二、算法设计1对于二维数组Amn,其中m=80,n=80，先读入m,n，然后读该数组的全部元素，对如下三种情况分别编写相应函数： （1）求数组A靠边元素之和 （2）求从A00开始的

20、互不相邻的各元素之和 （3）当m=n时，分别求两条对角线的元素之和，否则打印m!=n的信息2有数组A44，把1到16个整数分别按顺序放入A00.A03，A10.A13A20.A23，A30.A33中，编写一个函数获取数据并求出两条对角线元素的乘积。3只猴子要选大王，选举办法如下：所有猴子按1，2，.，n编号围坐一圈，从第1号开始按1、2、.、m报数，凡报m号的退出圈外，如此循环报数，直到圈内剩下一只猴子时，这只猴子就是大王。n和m由键盘输入，打印出最后剩下的猴子号。编写一个程序实现上述函数。4如果矩阵A中存在这样的一个元素Aij满足下列条件：Aij是第i行中值最小的元素，且又是第j列中最大的元

21、素，则称之为该矩阵的一个马鞍点。编写一个函数计算出m*n的矩阵A的所有马鞍点。5现有如下的稀疏矩阵A（如图所示），要求画出以下各种表示方法。 （1）三元组表示法 （2）十字链表法 15 0 0 22 0 -15 0 13 3 0 0 0 0 0 0 -6 0 0 0 0 0 0 0 0 91 0 0 0 0 0 0 0 28 0 0 06假设稀疏矩阵A和B（具有相同的大小m*n）都采用三元组表示，编写一个函数计算C=A+B，要求C也采用三元组表示。7假设稀疏矩阵A和B（分别为m*n和n*1矩阵）采用三元组表示，编写一个函数计算C=A*B，要求C也是采用稀疏矩阵的三元组表示。8假设稀疏矩阵只存放

22、其非0元素的行号、列号和数值，以一维数组顺次存放，行号为-1结束标志。 例如：如图所示的稀疏矩阵M，则存在一维数组D中： D0=1， D1=1，D2=1，D3=1，D4=5 D5=10，D6=3，D7=9，D8=5，D9= -1 M =: 1 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 现有两个如上方法存储的稀疏矩阵A和B，它们均为m行n列，分别存放在数组A和B中，编写求矩阵加法C=A+B的算法，C亦放在数组C中。已知A和B为两个n*n阶的对称矩阵，输入时，对称矩阵只输入下三角形元素，按压缩存储方法存入一维数组A和B中，编写一个计算

23、对称矩阵A和B的乘积的函数。10假设L为非递归并且不带共享子表的广义表，设计一个复制广义表L的算法。同步综合练习及参考答案（一） 基础知识题6.1 加设在树中，结点x是结点y的双亲时，用（x,y）来表示树变。已知一棵树边的集合为：（i,m）,（i,n）,（b,e）,（e,i）,（b,d）,（a,b）,（g,i）,（g,k）,（c,g）,（c,f）,（h,l）,（c,h）,（a,c）用树形表示法画出此树，并回答下列问题：（1） 哪个是根结点？（2） 哪些是叶结点？（3） 哪个是g的双亲？（4） 哪些是g的祖先？（5） 哪些是g的孩子？（6） 哪些是e的子孙？（7） 哪些是e的兄弟？哪些是f的兄弟？（8） 结点b和n的层次各是多少？（9） 树的深度是多少？（10） 以结点c为根的子树的深度是多少？（11） 树的度数是多少？解：（1） a是根结点。（2） m,n,j,k,l是叶结点。（3） c是g的双亲。（4） a,c是g的祖先。（5） g的孩子是j,k.。（6） e的子孙是 i,m,n.。（7） e的兄弟是a,f的兄弟是g。（8） h,b在第五层。（9） 树的深度为3。（10） 以C为根的子树的深度为3。（11） 树的度数为3。62 一