数据结构C语言版部分习题附标准标准答案.doc

个人收集整理 仅供参考学习第二章习题与解答一 判断题1线性表地逻辑顺序与存储顺序总是一致地.2顺序存储地线性表可以按序号随机存取.3顺序表地插入和删除操作不需要付出很大地时间代价，因为每次操作平均只有近一半地元素需要移动.4线性表中地元素可以是各种各样地，但同一线性表中地数据元素具有相同地特性，因此是属于同一数据对象.5在线性表地顺序存储结构中，逻辑上相邻地两个元素在物理位置上并不一定紧邻.6在线性表地链式存储结构中，逻辑上相邻地元素在物理位置上不一定相邻.7线性表地链式存储结构优于顺序存储结构.8在线性表地顺序存储结构中，插入和删除时，移动元素地个数与该元素地位置有关.9线性表地链式存储结构是用一组任意地存储单元来存储线性表中数据元素地.10在单链表中，要取得某个元素，只要知道该元素地指针即可，因此，单链表是随机存取地存储结构.二 单选题 (请从下列A，B，C，D选项中选择一项)1线性表是( ) .(A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空；(C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空.2对顺序存储地线性表，设其长度为n，在任何位置上插入或删除操作都是等概率地.插入一个元素时平均要移动表中地（）个元素.b5E2RGbCAP (A) n/2 (B) n+1/2 (C) n -1/2 (D) n p1EanqFDPw3线性表采用链式存储时，其地址( ) .(A) 必须是连续地； (B) 部分地址必须是连续地；(C) 一定是不连续地； (D) 连续与否均可以.4用链表表示线性表地优点是（ ）.(A)便于随机存取(B)花费地存储空间较顺序存储少(C)便于插入和删除(D)数据元素地物理顺序与逻辑顺序相同5 某链表中最常用地操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间.DXDiTa9E3d(A)单链表(B)双链表(C)单循环链表(D)带头结点地双循环链表6 循环链表地主要优点是( ).(A)不在需要头指针了(B)已知某个结点地位置后，能够容易找到他地直接前趋(C)在进行插入、删除运算时，能更好地保证链表不断开(D)从表中地任意结点出发都能扫描到整个链表7 下面关于线性表地叙述错误地是( ).(A) 线性表采用顺序存储，必须占用一片地址连续地单元；(B) 线性表采用顺序存储，便于进行插入和删除操作；(C) 线性表采用链式存储，不必占用一片地址连续地单元；(D) 线性表采用链式存储，不便于进行插入和删除操作；8 单链表中，增加一个头结点地目地是为了（）.(A) 使单链表至少有一个结点 (B)标识表结点中首结点地位置（C）方便运算地实现 (D) 说明单链表是线性表地链式存储9 若某线性表中最常用地操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间.RTCrpUDGiT(A) 单链表 (B) 仅有头指针地单循环链表(C) 双链表 (D) 仅有尾指针地单循环链表10 若某线性表中最常用地操作是取第i个元素和找第i个元素地前趋元素，则采用（）存储方式最节省运算时间（）.5PCzVD7HxA(A) 单链表 (B) 顺序表(C) 双链表 (D) 单循环链表三填空题1带头结点地单链表H为空地条件是_.1 非空单循环链表L中*p是尾结点地条件是_.3在一个单链表中p所指结点之后插入一个由指针f所指结点，应执行s-next=_;和p-next=_地操作.jLBHrnAILg4在一个单链表中p所指结点之前插入一个由指针f所指结点，可执行以下操作：s-next=_;p-next=s;t=p-data;p-data=_;s-data=_;5在顺序表中做插入操作时首先检查_.四算法设计题1 设线性表存放在向量Aarrsize地前elenum个分量中，且递增有序.试写一算法，将x 插入到线性表地适当位置上，以保持线性表地有序性.并且分析算法地时间复杂度.xHAQX74J0X2 已知一顺序表A，其元素值非递减有序排列，编写一个函数删除顺序表中多余地值相同地元素.3 编写一个函数，从一给定地顺序表A中删除值在xy(x=y)之间地所有元素，要求以较高地效率来实现.提示：可以先将顺序表中所有值在xy之间地元素置成一个特殊地值，并不立即删除它们，然后从最后向前依次扫描，发现具有特殊值地元素后，移动其后面地元素将其删除掉.LDAYtRyKfE4 线性表中有n个元素，每个元素是一个字符，现存于向量Rn中，试写一算法，使R中地字符按字母字符、数字字符和其它字符地顺序排列.要求利用原来地存储空间，元素移动次数最小.（研54）Zzz6ZB2Ltk5 线性表用顺序存储，设计一个算法，用尽可能少地辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换.即将线性表dvzfvkwMI1（a1, a2, , am, b1, b2, , bn）改变为：（b1, b2, , bn , a1, a2, , am）.6 已知带头结点地单链表L中地结点是按整数值递增排列地，试写一算法，将值为x 地结点插入到表L中，使得L仍然有序.并且分析算法地时间复杂度.rqyn14ZNXI7 假设有两个已排序地单链表A和B，编写一个函数将他们合并成一个链表C而不改变其排序性.8 假设长度大于1地循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点地指针，编写一个函数删除该结点地前趋结点.EmxvxOtOco9 已知两个单链表A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和B地交集C，要求C同样以元素递增地单链表形式存储.SixE2yXPq510 设有一个双向链表，每个结点中除有prior、data和next域外，还有一个访问频度freq域，在链表被起用之前，该域其值初始化为零.每当在链表进行一次Locata(L,x)运算后，令值为x地结点中地freq域增1，并调整表中结点地次序，使其按访问频度地递减序列排列，以便使频繁访问地结点总是靠近表头.试写一个算法满足上述要求地Locata(L,x)算法.6ewMyirQFL五上机实习题目1 Josephu 问题Josephu 问题为：设编号为1，2， n地n个人围坐一圈，约定编号为k（1=k0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码.开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m地人出列，将他地密码作为新地m值，从他地下一个人开始重新从1报数.如此下去，直到所有人全部出列为止.令n最大值取30.要求设计一个程序模拟此过程，求出出列编号序列.M2ub6vSTnP源程序代码：（在Tubro C 2.0测试通过）#include #include struct 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)0YujCfmUCw perror(malloc); return ptr1; head=ptr1; ptr1-next=head; for(i=1;inext=(struct node *)malloc(sizeof(struct node)=NULL)eUts8ZQVRd perror(malloc); ptr1-next=head; return head; ptr1=ptr1-next; ptr1-next=head; return head;main() int i,n=30,m; /* 人数n为30个 */ struct node *head,*ptr; randomize(); head=CreatList(n); for(i=1;inumber=i; head-cipher=rand(); head=head-next; m=rand(); /* m取随机数 */ i=0; /* 因为我没办法删除head指向地节点，只会删除head地下一节点，所以只能从0数起.*/sQsAEJkW5T while(head-next!=head) /* 当剩下最后一个人时，退出循环 */ if(i=m) ptr=head-next; /* ptr记录数到m地那个人地位置 */ printf(number:%dn,ptr-number); printf(cipher:%dn,ptr-cipher); m=ptr-cipher; /* 让m等于数到m地人地密码 */ head-next=ptr-next; /* 让ptr从链表中脱节，将前后两个节点连接起来 */ head=hea/d-next; /* head移向后一个节点 */ free(ptr); /* 释放ptr指向地内存 */ i=0; /* 将i重新置为0，从0再开始数 */ else head=head-next; i+; printf(number:%dn,head-number); printf(cipher:%dn,head-cipher); free(head); /* 让最后一个人也出列 */第三章习题一、 基本题1填空：线性表、栈和队列都是_结构，可以在线性表地_位置插入和删除元素，对于栈只能在_位置插入和删除元素，对于队只能在_位置插入和_位置删除元素.GMsIasNXkA2. 栈和队列数据结构地特点，什么情况下用到栈，什么情况下用到队列？3设有编号为1，2，3，4地四辆车，顺序进入一个栈式结构地站台，试写出这四辆车开出车站地所有可能地顺序（每辆车可能入站，可能不入站，时间也可能不等）.TIrRGchYzg4试证明：若借助栈由输入序列1，2， ，n得到输出序列为p1p2pn (它是输入序列地一个排列)，则在输出序列中不可能出现这样地情形：存在着ijk，使得pjpk pi.7EqZcWLZNX二、 设计算法题1 假设称正读和反读都相同地字符序列为“回文”，例如，“abcddcba”、“qwerewq”是回文，“ashgash”不是回文.是写一个算法判断读入地一个以为结束符地字符序列是否为回文.lzq7IGf02E2 设以数组sem存放循环队列地元素，同时设变量rear 和front分别作为队头队尾指针，且队头指针指向队头前一个位置，写出这样设计地循环队列入队出队地算法.zvpgeqJ1hk3 假设以数组sem存放循环队列地元素，同时设变量rear 和num分别作为队尾指针和队中元素个数记录，试给出判别此循环队列地队满条件，并写出相应入队和出队地算法.NrpoJac3v14 假设以带头结点地循环链表表示一个队列，并且只设一个队尾指针指向尾元素结点（注意不设头指针），试写出相应地置空队、入队、出队地算法.1nowfTG4KI5 设计一个算法判别一个算术表达式地圆括号是否正确配对.6 写一个算法，借助于栈将一个单链表置逆.7两个栈共享向量空间vm，它们地栈底分别设在向量地两端，每个元素占一个分量，试写出两个栈公用地栈操作算法：push(i,x)、pop(i)和top(i)，i=0和1 ,用以指示栈号.fjnFLDa5Zo三、 实验题目1 背包问题地求解：假设有一个能装入总体积为T地背包和n件体积分别为w1 , w2 , , wn 地物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + + wn=T，要求找出所有满足上述条件地解.例如：当T=10，各件物品地体积1，8，4，3，5，2时，可找到下列4组解：（1，4，3，2）tfnNhnE6e5（1，4，5）（8，2）（3，5，2）.提示：可利用回溯法地设计思想来解决背包问题.首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止.但如果在剩余地物品中找不到合适地物品以填满背包，则说明“刚刚”装入背包地那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”地物品中选取，如此重复，直至求得满足条件地解，或者无解.HbmVN777sL由于回溯求解地规则规则是“后进先出”因此自然要用到栈.2 模拟停车厂管理地问题.设停车厂只有一个可停放几辆汽车地狭长通道，且只有一个大门可供汽车进出.汽车在停车场内按车辆到达地先后顺序依次排列，若车场内已停满几辆汽车，则后来地汽车只能在门外地便道上等候，一旦停车场内有车开走，则排在便道上地第一辆车即可进入；当停车场内某辆车要离开时，由于停车场是狭长地通道，在它之后开入地车辆必须先退出车场为它让路，待该辆车开出大门后，为它让路地车辆再按原次序进入车场.在这里假设汽车不能从便道上开走.试设计一个停车场管理程序.V7l4jRB8Hs第四章习题算法设计题1利用C地库函数strlen,strcpy和strcat写一个算法void StrInsert(char *S,char *T,int t) ，将串T插入到S地第i个位置上.若i大于S地长度，则插入不执行.83lcPA59W92利用C地库函数strlen,strcpy（或strncpy）写一个算法void StrDelete(char *S,int t,int m) ，删除串S中从位置I开始地连续地m个字符.若istrlen(S)，则没有字符被删除；若i+mstrlen(S)，则将S中从位置i开始直至末尾地字符均被删去.mZkklkzaaP3采用顺序结构存储串，编写一个函数，求串和串地一个最长地公共子串.4采用顺序存储结构存储串，编写一个函数计算一个子串在一个字符串中出现地次数，如果该子串不出现则为0.AVktR43bpw第五章习题一、单项选择题1. 二维数组M地成员是6个字符（每个字符占一个存储单元）组成地串，行下标i地范围从0到8，列下标j地范围从1到10，则存放M至少需要（1）个字节；M地第8列和第5行共占（2）个字节；若M按行优先方式存储，元素M85地起始地址与当M按列优先方式存储时地（3）元素地起始地址一致.（）ORjBnOwcEd（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.M092MiJTy0dTT2. 二维数组M地元素是4个字符（每个字符占一个存储单元）组成地串，行下标i地范围从0到4，列下标j地范围从0到5，M按行存储时元素M35地起始地址与M按列存储时元素（1）地起始地址相同.（）gIiSpiue7A A.m24 B.M34 C.M35 D.M44 3. 数组A中，每个元素A地存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要地单元个数是（1），若该数组按行存放时，元素A85地起始地址是（2），若该数组按列存放时，元素A85地起始地址是（）.uEh0U1Yfmh（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. 三元组和散列 C.三元组和十字链表 D. 散列和十字链表5.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素地行下标和列下标互换，就完成了对该矩阵地转置运算，这种观点（）IAg9qLsgBX A.正确 B.错误6.假设按行优先存储整数数组A9358时，第一个元素地字节地址时，每个整数占个字节.问下列元素地存储地址是什么.WwghWvVhPE(1) a0000 (2)a1111 (3)a3125 (4)a82477.设有三对角矩阵Ann，将其三条对角线上地元素存于数组B3n中，使得元素Buv=aij，试推倒出从（i,j）到 (u,v)地下标变换公式.asfpsfpi4k8.假设一个准对角矩阵：a11 a12a21 a22a33 a34a43 a44 . aij a2m-1,2m-1 a2m-1,2m a2m,2m-1 a2m,2m ooeyYZTjj1按以下方式存储于一维数组B4m中:01 2 3 4 5 6 k 4m-1 4mA11a12a21a22a33a34a43aija2m-1,2ma2m,2m-1a2m,2m写出由一对下标（i,j）求k地转换公式. 9.画出下列广义表地存储结构式意图.（） A=(a,b,c),d,(a,b,c)（） B=(a,(b,(c,d),e),f)二、算法设计1对于二维数组Amn,其中m=80,nn0+=1+n2+(m-1)nM6.5 一个深度为h地满k叉树有如下性质：第h层上地结点都是叶子结点，其余各层上每个结点都有k棵非空子树.如果按层次顺序（同层自左至右）从未有过开始对全部结点编号，问：4B7a9QFw9h（1） 各层地结点数目是多少？（2） 编号为i地结点地双亲结点（若存在）地编号是多少？（3） 编号为i地结点地第j个孩子结点（若存在）地编号是多少？（4） 编号为i地结点有右兄弟地条件是什么？其右兄弟地编号是多少？解：（1） Ki-1（2）（3） Ki+j-1（4） (i-1)MOD K0 ,i+166 高度为h地完全二叉树至少有多少个结点？至多有多少个结点？解：至少有：2h-1，至多有：2h-167 在具有n个结点地k叉树（k2）地k叉树链表表示中，有多少个空指针？解：（k-1）n+1个空指针68 假设二叉树包含地结点数据为1，3，7，2，12.（1） 画出两棵高度最大地二叉树；（2） 画出两棵完全二叉树，要求每个双亲结点地值大于其孩子结点地值.69 试找出分别满足下面条件地所有二叉树：（1）前序序列和中序序列相同；（2）中序序列和后序序列相同；（3）前序序列和后序序列相同；（4）前序、中序、后序序列均相同.解：（1） 空二叉树或任一结点均无左子树地非空二叉树（2） 空二叉树或任一结点均无左子树地非空二叉树（3） 空二叉树或仅有一个结点地二叉树（4） 同（3）610 试采用顺序存储方法和链接存储方法分别画出6. 30所示各二叉树地存储结构.解：顺序存储：(a)1 2 3 4 5(b)1 2 3 4 5(c)1 2 3 4 5 6 7 8 (d)1 2 3 4 5 6 7 8 9连接存储：611 分别写出图6.30所示各二叉树地前序、中序和后序序列.解：612 若二叉树中个结点地值均不相同，则由二叉树地前序序列和中序序列，或由其后序序列地中序列均能惟一地确定一棵二叉树，但由前序序列和后序序列却不一定能惟一地确定一棵二叉树.ix6iFA8xoX（1） 已知一棵二叉树地前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树.（2） 已知一棵二叉树地中序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树.（3） 已知两棵二叉树前序序列和后序序列均为AB和BA，请画出这两棵不同地二叉树.解：613 对二叉树中结点进行按层次顺序（每一层自左至右）地访问操作称为二叉树地层次遍历，遍历所得到地结点序列称为二叉树地层次序列.现已知一棵二叉树地层次序列为ABCDEFGHIJ，中序序列为DBGEHJACIF，请画出该二叉树.wt6qbkCyDE解：614 试画出图6.30所示各二叉树地前序、中序和后序线索树及相应地线索链表.解：（以c为例） 前序：1 2 3 5 7 8 6 4 前序：1 7 5 8 3 6 2 4615 在何种线索树中，线索对所求指定结点在相应次序下地前趋和后继并无帮助？解：在前序线索树中找某一点地前序前趋以及在后序线索树中寻找某一点地后继，线索并无多大帮助.616 对图6.31所示地森林：（1） 求各树地前序序列和后序序列：（2） 求森林地前序序列和后序序列：（3） 将此森林转换为相应地二叉树：（4） 给出（a）所示树地双亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄弟链表表示等四种存储结构，并指出哪些存储结构易于求指定结点地祖先，哪些易于求指定结点地后代？Kp5zH46zRk解： (1) a b cYl4HdOAA61前序 ABCDEF GHIJK LMPQRNO后序 BDEFCA IJKHG QRPMNOL(2) 前序： ABCDEFGHIGKLMPQRNO 后序： BDEFCAIJKHGQRPMNOL(3) 二叉树(4) 1 孩子链表表示发： 双亲链表表示发：结点 0 1 2 3 4 5 6data A B C D E Fparent -1 0 1 1 3 3 3 双亲孩子链表： 孩子兄弟链表表示： 易于求祖先：双亲链表面双亲孩子 易于求后代：孩子链表双亲孩子617 画出图6.32所示地各二叉树所应地森林618 高度为h地严格二叉树至少有多少个结点？至多有多少个结点？解：最多有2n-1 最少有 2n-1619 在什么样地情况下，等长编码是最优地前缀码？解：当字符集中地各字符使用频率均匀时.620 下属编码哪一组不是前缀码？ 00，01，10，11，0，1，00，11，0，10，110，111解：因为前缀码中不可能存在一个元素是另一个地前面部分.所以第二组不是.620 假设用于通信地电子由字符集a,b,c,d,e,f,g,h中地字母构成，这8个字母在电文中出现地概率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10ch4PJx4BlI（1） 为这8个字母设计哈夫曼编码.（2） 若用三位二进制数（07）对这个8个字母进行等长编码，则哈夫曼编码地平均码长是等长编码地百分之几？它使电文总长平均压缩多少？qd3YfhxCzo解：哈夫曼编码码长： 4*0.07+2*0.19+5*0.02+4*0.06+5*0.03+2*0.21+4*0.1=2.71E836L11DO5 等长码长： 3905 平均缩了10%（二） 算法设计题 6.22 二叉树地遍历算法可写为通用形式.例如，通用地中序遍历为：void Inorder(BinTree T,void(*Visit)(Datatype x) if (T) Inorder(T-lchild,Visit); /*遍历左子树*/ Visit(T-data); /*通过函数指针调用它所指地函数来访问结点*/ Inorder(T-rchild,Visit); /*遍历右子树*/ 其中Visit是一个函数指针，它指向形如void f（DdataType x）地函数.因此我们可以将访问结点地操作写在函数f中，通过调用语句Inorder（root，f）将f地地址传递给Visit，来执行遍历操作.请写一个打印结点地数据地函数，通过调用上述算法来完成书中6.3节地中序遍历.S42ehLvE3M解： #include“stdio.h” #define Null 0 typedef char DataType; typedef struct no