数据结构 习题Word下载.docx

1、 ）A.p=p- B、 p-next-C.p- D.p=p-12在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p-next=head,则（A.p指向头结点 B.p指向尾结点C.*p的直接后继是头结点 D、 *P的直接后继是尾13.为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构宜采用（ ）方式。A、顺序存储 B.链式存储C.索引存储 D.散列存储答案：1-5 BDACB 6-10 DBABC 11-13 BDA二、判断题（判断下列各小题，正确的在题后括号内打“”，错的打“”。）1、单链表中的头结点就是单链表的第一个结点。（ ）2、所谓数据的逻辑结构

2、指的是数据元素之间的逻辑关系。（ ）3、在线性结构中，每个结点都有一个直接前驱和一个直接后继。三、填空题1、在单链表中设置头结点的作用_ 。2、.设head为带有头结点的单链表的头指针，则判断单链表为空的条件是：_。3、.带头结点的循环链表L为空表的条件是_ _ _。带头结点的双循环链表L为空表的条件是_ 。4、在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是_ _和_。5、.通常单链表的头结点指的是_ _；单链表的首结点指的是_ _。6、在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用

3、p表示为 。7、从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需_ _一个位置。1、简化插入删除算法. 2、head-next= =NULL_。3、 L-next=L _。L-next=L-prior=L 4、_s-next_和_p-next=s_。5、_在单链表第一个结点之前增设的一个类型相同的结点_； _表结点中的第一个结点_。6、pnextnext=head 。7、_向前移动_四、算法阅读题 1、阅读下面的算法 LinkList mynote（LinkList L） /L是不带头结点的单链表的头指针 if（L&next） q=L；L=Lnext；p=L； S1： while（p

4、next） p=p S2： pnext=q；qnext=NULL； return L； 请回答下列问题： （1）说明语句S1的功能； （2）说明语句组S2的功能； （3）设链表表示的线性表为（a1,a2, ,an）,写出算法执行后的返回值所表示的线性表。（1）查询表的尾节点 （2）将第一个节点链接到表的尾部成为新的尾节点（3）（a2,a3,.an,a1）2、以下函数中，h是带头结点的双向循环链表的头指针。 （1）说明程序的功能； （2）当链表中结点数分别为1和6（不包括头结点）时，请写出程序中while循环体的执行次数。 int f（DListNode *h） DListNode *p,*q;

5、 int j=1; p=h- q=h-prior; while（p!=q | p-prior!=q）&（j!=0） if（p-data=q-data） p=p- q=q- else j=0; return j;（1）是否对称（2）1-0；6-3五、应用题1、假定在学生的档案中含有：姓名、学号、年龄、性别。如采用线性表作为数据结构来实现档案管理问题，分别给出线性表的在顺序实现下的类型定义和在链接实现下的类型定义。2.假设以带头结点的单循环链表作非递减有序线性表的存储结构。请设计一个时间复杂度为O（n）的算法，删除表中所有数值相同的多余元素，并释放结点空间。例如：（7，10，10，21，30，42

6、，42，42，51，70）经算法操作后变为（7，10，21，30，42，51，70）参考答案：typedef struct node int data; struct node * next;LinkList;Delete_Eq（LinkList * head） LinkList * p, * q, * s; p=head; do q= p-if（p-data = = q-data） s= q; free（s）; q = q-else p=q;while（p-next != head）;2、线性表逆置void Convers（LinkList *head） LinkList * p, *q,

7、*r; p = head; q = p-next = NULL; while （ q!= NULL） r=q- q- q=r; head = p;栈和队列习题1. 简述下面所给算法的功能是什么？（假设栈元素为整数类型） （1） void ex31（SeqStack *S）int A80,i,n; n=0; while（!empty（S） An=popS; n+; for（i=0;ik）项（f0,f1,f2,）的算法，其函数定义如下： 0 n=0f（n）= 1 n=1 f（n-2）+f（n-1） n=2算法如下：因为循环队列长度为K，所以在执行算法结束时，留在队列中的元素应是所求序列中的最后k项

8、。由于只有k个元素空间，则在计算fi时，队列总是处在头尾相接的状态，因此只须一个指针rear 指向当前的队尾。每次求得一个fi之后即送入（rear% k）的位置上，冲掉原来对头元素。#define m maxlentypedef struct int rear; int datam;CirQueue;int Fibonacci（int i） /求序列的前n项算法 if（i = 0） return 0; else if（i= = 1） return 1; else return （Fibonacci（i-2） +Fibonacci（i-1）;void Fibonacci（ CirQueue *

9、Q, int k） int i, n; Q-rear = 0; scanf（“%d” ,&n）; for（i =0; irear =i; if （ i =k） Q-rear = Q-rear% k;data Q-rear = Fibonacci（i）; 3算法阅读假设两个队列共享一个循环向量空间（参见右下图）， 其类型Queue2定义如下： typedef struct DateType dataMaxSize； int front2,rear2； Queue2；对于i=0或1，fronti和reari分别为第i个队列的头指针和尾指针。请对以下算法填空，实现第i个队列的入队操作。 int En

10、Queue （Queue2 *Q,int i,DateType x） /若第 i个队列不满，则元素x入队列，并返回1；否则返回0 if（i1）return 0； if（Qreari=Qfront return 0； Qdata =x；reari= ; return1；（i1）%2（或1i） Qreari （Qreari1）%Maxsize4、假定在一个链队列中只设置队列为指针，不设置对首指针，并且让队尾节点的指针域指向队首节点（称此微循环队列），试分别写出在循环链队上进行插入和删除操作的算法。插入算法：void QInsert（LNode * &Rear , const Elemtype &

11、item） LNode * newptr = new LNode ; if（newptr = = NULL） printf（“wrong”）; exit（1）; newptr -data =item; if（Rear = = NULL） Rear = newptr -next = newptr; else newptr-next =Rear - Rear - Rear = newptr;删除算法：ElemType QDelte（LNode * & Rear） if（Rear = =NULL） printf（“Linked queue is empty ！”）；LNode * p = Rear

12、-if（ p = = Rear） Rear =NULL;next = p-ElemType temp = p-data;free（p）;return temp;第四章 串习题练习：1、串长度的定义是（ ） A.串中不同字母的个数 B.串中不同字符的个数 C.串中所含字符的个数，且大于0 D. 串中所含字符的个数2、如下陈述中正确的式（ ）。A、串是一种特殊的线性表 B、串的长度必须大于0 C、串中元素只能是字母 D、空串就是空白串3、设字符串s1=”abcdefg”,s2=”pqrst”,则运算s=strcat（substr（s1,2,length（s2）,substr（s1,length（s

13、2）,2）后串值为（ ）。 A.“bsdefef” B.“bcpqrst” C.“bsdefg” D.“bcdef” 4、设有两个串s和t,求t在s中首次出现的位置的运算是（ ） A.连接 B.模式匹配 C.求子串 D.求串长一、例子例1：从串s1（为顺序存储结构）中第k个字符起求出首次与字符串s2相同的子串的起始位置。分析：从第k个元素开始扫描s1 ，当其元素值与s2第一个元素值相同时，判断它们之后的元素值是否依次相同，直到s2结束为止。若都相同则返回当前位置值，否则继续上述过程直到s1扫描完为止。 #define MaxStrSize 256 typedef struct char chM

14、axStrSize; int Len; SeqString; int PartPosition（SeqString *s1, SeqString *s2,int k） int i,j; i=k; /*作为扫描s1的下标*/ j=1； /*作为扫描s2的下标*/ while（ilen&jlen） if（s1-chi=s2-chj） i+;j+; else i=i-j+2; j=1;if（js2- return i-s2-len; return 0;例2：从串s中删除所有与串t 相同的子串。 分析：可利用前面题目的函数。从位置1开始调用函数PartPosition（）,若找到了相同的子串，则调用删

15、除子串函数DelSubstring（）将其删除，再查找后面位置的相同子串，方法与前同。 void DelSubstring（SeqString *s,SeqString *t） int j,k,i=1; k=1;while（ilen）&（k!=0） if（k=PartPosition（s,t,i）0） for（j=k+t-j+） s-chj-t-len=s-chj;/*删除从k开始的子串*/len=s-len-t-len /*修改s串的长度*/i=k; s-chs-len=0; /*赋一个串结束符*/例3：已知S和T是用结点大小为1的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现

16、的字符。根据题意，要用到两重循环，从S中取出第一个字符，与T串中的每个 字符依次进行比较，如果一直没有遇到相等的字符，则S中取出的字符就是要求的字符，退出循环；若遇到相同的字符，则再从S中取出第二个字符与T中的字符进行比较，依次进行下去。 算法如下：char data;struct node *next;LinkStrNode;typedef LinkStrNode *LinkString;char FindChar（LinkString S, LinkString T） LinkStrNode *p,*q;P=S;While（p!=NULL）q=T; while（q! if（p-data!=

17、q- /继续下一个字符的比较 break; /若有相同的字符，跳出内循环 if（q=NULL） return p- /返回要求的字符p=p- return “#”; /没有要求的字符二、算法设计题1、试写一算法，实现顺序串的比较运算strcmp（S,T）,当ST时，函数值为1，当S=T时，函数值为0，当ST.chi） else if（S.chi return 12、已知采用顺序存储结构的串S，试写一个算法删除S中第i个字符开始的j个字符。 先判断i和j是否在有效范围内（即i+jS- printf（“i或j超出有效范围”）; for（k=i+j-1;kchk-j=S-chk; /移位删除j个字符

18、。len=S-len-j; /串长度减13、设S和T是两个采用顺序结构存储的串，试写一个算法将串S中的第i个字符开始的j个字符用串T替换。SeqSAtring *replace（SeqString *S, SeqString *T,int i,int j） int k,l; k=T- if（k0） /说明T的长度大于被替换的串的长度，因此S串需要后移 for（l=S-len-1;l=i+T-l-）chl+k=S-chl; for（l=i+T-ll+） /说明T的长度小于被替换的串的长度，因此S串需要前移 for（l=0;T-chi+l-1=T- /插入串Tlen+T- /修改串S的串长度 Re

19、turn S; /返回串S第五章 多维数组和广义表一、应用题（1）已知二维数组Am*n按“行优先顺序”存储在内存中，假设每个元素占d个存储单元，第一个元素的存储地址表示为LOC（A00）,那么计算数组A的任意元素Aij的存储地址公式是什么？LOC（aij）=LOC（a00）+（i*n+j）*d （2）已知二维数组A510按“行优先顺序”存储在内存中，假设每个元素占3个存储单元，第一个元素的存储地址表示为1000,那么计算数组A的A34的存储地址。LOC（A234=LOC（A00）+（3*10+4）*3（3）已知一个10阶对称矩阵A,采用压缩存储方式存储（以行序为主，每个元素占一个单元），起始地

20、址为1100，则A45的地址多少？因为A是对称矩阵，A45又在上三角，所以存储位置k=j*（j-1）/2+i-1= ,因此，A45的存储地址为LOC（SA）+k*d=二、自测题1、 一维数组和线性表区别是：（ ）A。前者长度固定，后者长度可变 B.长度均可变C.无区别 D. 长度均固定2、稀疏矩阵一般存储方法有两种（ ）和（ ）3、N是一个5*8的二维数组，当M按行序方式存储时，表示该数组的第十个元素是（ ）。N22 B、N21 C、N11 D、N12 树习题一、1.深度为K的完全二叉树至少有_个结点，至多有_个结点。.（1）2k-1（2）2k-1。2.树的三种常用存储结构是：孩子链表表示法、

21、_和_。 （1）孩子兄弟链表示法 （2）双亲表示法。3.在有n个结点的二叉链表中，值为非空的链域的个数为（ ） A. n-1 B. 2n-1 C. n+1 D. 2n+14.一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为（ ） A. 0 B. 1 C. 2 D.不确定5.一棵树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定_。2. 左右子树空6.有64个结点的完全二叉树的深度为（ ）（根的层次为1）。 A. 8 B. 7 C. 6 D. 57.二叉树在线索化后，仍不能有效求解的问题是（ ） A.先序线索二叉树中求先序后继 B.中序线索二叉树中求中序后继 C.中序线索二叉树中求中序前趋 D.后序线索二叉树中求后序后继8在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为（ ） A4 B5 C6 D79.具有N个结点的完全二叉树的深度