数据结构各章复习题.docx

《数据结构各章复习题.docx》由会员分享，可在线阅读，更多相关《数据结构各章复习题.docx（68页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构期末复习题及答案全集 第 1 章 绪论 一填空题 1. 数据结构被形式地定义为（D, R），其中D是 的有限集合，R是D上的 有限集合。 2. 数据结构包括数据的 、数据的 和数据的 这三个方面的内容。 3. 数据结构按逻辑结构可分为两大类，它们分别是 和 。 4. 线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。 5在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 后续结点，其余每个结点有且只有1个后续结点。 6. 在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点；叶子结点没有 结点，其余

2、每个结点的后续结点数可以 。 7. 在图形结构中，每个结点的前驱结点数和后续结点数可以 。 8. 数据的存储结构可用四种基本的存储方法表示，它们分别是 。 9数据的运算最常用的有5种，它们分别是 。 10. 一个算法的效率可分为 效率和 效率。 11数据结构是研讨数据的_（1）_和_（2）_，以及它们之间的相互关系，并对与这种结构定义相应的_（3）_，设计出相应的（4）_。 12. 下面程序段中带下划线的语句的执行次数的数量级是( )。 i:=1; WHILE i0）。 A表元素 B字符 C数据元素 D数据项 （ A ）12若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运

3、算，则利用_ 存储方式最节省时间。 A顺序表 B双链表 C带头结点的双循环链表 D单循环链表 （ D ）13某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用 _ 存储方式最节省运算时间。 A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表（ B ）14. 静态链表中指针表示的是_. A 内存地址 B数组下标 C下一元素地址 D左、右孩子地址（ B ）15. 链表不具有的特点是_. A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比 （ D ）16完成在双循环链表结点p之后插入s的操作是（ ）.

4、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; （ B ）17在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。 Ap-next=s;s-next=p-nex

5、t; B s-next=p-next;p-next=s; Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s; （ B ）18对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ） Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL （ A ）19. 在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。 A (p.llink).rlink:=p.rlink (p.rlink).llink:=p.llink; B p.llink:=(p.llink).llink (p.l

6、link).rlink:=p; C (p.rlink).llink:=p p.rlink:=(p.rlink).rlink D p.rlink:=(p.llink).llink p.llink:=(p.rlink).rlink; 三、简答题 1线性表有两种存储结构：一是顺序表，二是链表。试问： （1） 如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？ 答:在此情况下,应该使用链式存储结构.因为,链式表可以很好地处理插入删除操作,而使用顺序存储结构则可能发生溢出,又有可能因为预分配的空间过大造成浪费. （2）

7、 若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？ 答:应选用顺序存储结构,因为,单链表查找元素的时间复杂度为 O(1). 2 . 在单链表中设置头结点的作用是什么？ 答:将空表与非空表,头尾结点与其它结点的操作统一. 四、线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表 L=23，17，47，05，31，若它以链接方式存储在下列 100119 号地址空间中，每个结点由数据（占 2 个字节）和指针（占 2 个字节）组成，如下所示： 05 U 17 X 23 V 31 Y 47 Z 100 120 其中

8、指针 X，Y，Z 的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？ 答: X 的值为 116 , Y 的值为 NULL , Z 的值为 100 .首结点起始地址为 108,末结点的起始地址为 112 . 五、编程题 1. 写出顺序创建单链表的程序，即按从 a1 到 an 顺序创建。 此文件名为 MyLinkList.cpp#include s-data=ai; using namespace std; s-next=first-next; template first-next=s; struct Node T data; template Node *next; Li

9、nkList : LinkList() ; template Node *q; class LinkList Node *p; p=first; private: while(p) Node *first; public : q=p; LinkList(T a,int n); p=p-next; LinkList(); delete q; void PrintList(); ; template void main() LinkList:LinkList(T a,int n) int r=1,2,3,4,5; first=new Node; LinkLista(r,5); first-next

10、=NULL; a.PrintList (); for(int i=0;in;i+) system(pause); Node *s; s=new Node; 2. 已知一个带头结点的单链表 L，请编程求该单链表中数据元素的个数。 由于已知一个单链表 L,所以把上一道题的代码引 i+; 过来 p=p-next; #include #include “MyLinkList.cpp” return i; using namespace std; template void main() int LinkList:getLongth() LinkList L; Node *p; L.getLongth(

11、); int i=0; system(pause); p=first-next; while(p) 3. 设有一带头结点的单链表,编程将链表颠倒过来，即（a1.an）逆置为(an.a1)，要求不用另外的数组或结点完成. #include using namespace std; template q=p; struct Node p=p-next; delete q; T data; Node *next; ; template template int LinkList:getLongth() class LinkList Node *p; private: int i=0; Node *f

12、irst; p=first-next; public : while(p) LinkList() first=new Node;first-next=NULL; i+; LinkList(int n); p=p-next; LinkList(); Node* getFirst() return i; return this-first; template void LinkList:TurnLinkList() void PrintList(); int getLongth(); Node *p,*q,*r; void TurnLinkList(); p=first-next ; ; q=p-

13、next ; template while(q!=NULL) LinkList:LinkList(int n) r=q-next ; first=new Node; q-next =p; first-next=NULL; p=q; for(int i=0;in;i+) q=r; Node *s; first-next-next =NULL; s=new Node; first-next =p; cout请输入第i+1个数据元素 : template ; void LinkList:PrintList () cins-data; s-next=first-next; Node *p; first

14、-next=s; p=first-next; while(p != NULL) template coutdata ; LinkList : LinkList() p=p-next ; Node *q; coutendl; Node *p; p=first; void main() while(p) int n; A.PrintList(); cout请输入单链表需要输入的数据元素的 cout颠倒之后的数据元素依次为: n; A.PrintList(); LinkList A(n); system(pause); coutA的数据元素为 : ; 4请写一个算法将顺序存储结构的线性表（a1.an

15、）逆置为(an.a1)，要求使用最少的附加空间。 Status ListReplace_Sq(SqList &L,int n) If(nL.length+1) return ERROR; if(L.length=L.listsize) Newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType); If(!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; for(i=0;itop0 ST-top=0 ST-topm

16、0 ST-top=m0 （ D ）4. 判定一个队列 QU（最多元素为 m0）为满队列的条件是 QU-rear QU-front = = m0 QU-rear QU-front 1= = m0 QU-front = = QU-rear QU-front = = QU-rear+1 （ D ）5数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为 （）rf; （）（nfr）% n; （）nrf; （）（nrf）% n 6. 设有 4 个数据元素 a1、a2、a3 和 a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按 a

17、1、a2、a3、 a4 次序每次进入一个元素。假设栈或队的初始状态都是空。 现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A ，第二次出栈得到的元素是 B ；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C ，第二次出队得到的元素是 D 。经操作后，最后在栈中或队中的元素还有 E 个。 供选择的答案： AD：a1 a2 a3 a4 E： 1 2 3 0 答：A、B、C、D、E分别为 、 、 、 、 7. 栈是一种线性表，它的特点是 A 。设用一维数组 A*1,n+来表示一个栈，An为

18、栈底，用整型变量 T 指示当前栈顶位置，AT为栈顶元素。往栈中推入（PUSH）一个新元素时，变量 T 的值 B ；从栈中弹出（POP）一个元素时，变量 T 的值 C 。设栈空时，有输入序列 a，b，c，经过 PUSH，POP，PUSH，PUSH，POP 操作后，从栈中弹出的元素的序列是 D ，变量 T 的值是 E 。 供选择的答案： A： 先进先出 后进先出 进优于出 出优于进 随机进出 B，C： 加 1 减 1 不变 清 0 加 2 减 2 D： a,b b,c c,a b,a c,b a,c E： n+1 n+2 n n-1 n-2 答：A、B、C、D、E分别为 、 、 、 、 8. 在做

19、进栈运算时，应先判别栈是否 A ；在做退栈运算时，应先判别栈是否 B 。当栈中元素为 n 个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 。 为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 D 分别设在这片内存空间的两端，这样，只有当 E 时，才产生上溢。 供选择的答案： A，B：空 满 上溢 下溢 C： n-1 n n+1 n/2 D： 长度 深度 栈顶 栈底 E：两个栈的栈顶同时到达栈空间的中心点 其中一个栈的栈顶到达栈空间的中心点 两个栈的栈顶在达栈空间的某一位置相遇 两个栈均不空，且一个栈的栈顶到达另一个栈的栈底 答：A、B、C、D、E分

20、别为 、 、 、 、 四、简答求解题 1. 说明线性表、栈与队的异同点。 答: 相同点: 逻辑结构相同,都是线性的.都可以用顺序存储结构或链式存储结构.栈和队列是两种特殊的线性表,即受限的线性表(只是对插入和删除运算加以限制). 不同点: 1.运算规则不同,线性表是随机存取的,而栈是只允许在一端进行插入和删除运算的,因而是后进先出表 LIFO;队列是只允许在一端进行插入,另一端进行删除运算,因而是先进先出表 FIFO. 2.用途不同,线性表比较通用,堆栈用亍函数调用,递归和筒化设计等.队列用亍离散事件模拟,多道作业处理和筒化设计等. 2. 设循环队列的容量为 40（序号从 0 到 39），现经

21、过一系列的入队和出队运算后，有 front=11，rear=19; front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？答: 第一种情况下,代入公式(40+19-11)%40=8 , 所以有元素 8 个. 第二种情况下,代入公式(40+11-19)%40=32 , 所以有元素 32 个. 五、算法设计 1. 假设一个数组 squm存放循环队列的元素。若要使这 m 个分量都得到利用，则需另一个标志 tag，以 tag 为 0 或 1 来区分尾指针和头指针值相同时队列的状态是“空”还是“满”。试编写相应的入队和出队的算法。 #define MAXQSIZE 100 typ

22、edef struct QElemType *base; int front; int rear; SqQueue; Status InitQueue(SqQueue &Q,int maxsize) Q.base=(QElemType*)malloc(maxsize*sizeof(QElemType); if(!Q.base) exit(OVERFLOW); Q.front=Q.rear=0; tag=0; return OK; Status EntryQueue(Queue &Q,QElemType e) if(Q.rear=Q.front|tag=1) return ERROR; Q.ba

23、seQ.rear=e; Q.rear=(Q.rear+1)%MAXSIZE; return OK; Status DeleteQueue(Queue &Q,QElemType &Q) if(Q.front=Q.rear|tag=0) return ERROR; e.Q.baseQ.front; Q.front=(Q.front+1)%MAXSIZE; return TRUE; 第 45 章 串、数组和广义表 一、填空题 1. 称为空串； 称为空白串。 2. 设 S=“A;/document/Mary.doc”，则 strlen(s)= , “/”的字符定位的位置为 。 3. 子串的定位运算称为

24、串的模式匹配； 称为目标串， 称为模式。 4. 若 n 为主串长，m 为子串长，则串的古典匹配算法最坏的情况下需要比较字符的总次数为 。 5. 假设有二维数组 A68，每个元素用相邻的 6 个字节存储，存储器按字节编址。已知 A 的起始存储位置（基地址）为 1000，则数组 A 的体积（存储量）为 ；末尾元素 A57 的第一个字节地址 为 ；若按行存储时，元素 A14 的第一个字节地址为 ；若按列存储时，元素 A47 的第一个字节地址为 。 6. 设数组 a160, 170的基地址为 2048，每个元素占 2 个存储单元，若以列序为主序顺序存储，则元素 a32,58 的存储地址为 。 7. 三

25、元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素 的 、 和 。 8. 求下列广义表操作的结果： （1） GetHead【(a,b),(c,d)】= ; （2） GetHead【GetTail【(a,b),(c,d)】= ; （3） GetHead【GetTail【GetHead【(a,b),(c,d)】= ; （4） GetTail【GetHead【GetTail【(a,b),(c,d)】= ; 二、单选题 （ ）1. 串是一种特殊的线性表，其特殊性体现在： 可以顺序存储 数据元素是一个字符 可以链式存储 数据元素可以是多个字符 （ ）2. 设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作： 连接 模式匹配 求子串 求串长 （ ）3. 设串 s1=ABCDEFG，s2=PQRST，函数 con(x,y)返回 x 和 y 串的连接串，subs(s, i, j)返回串 s 的从序号 i开始的 j 个字符组成的子串，len(s)返回串 s 的长度，则 con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)的结果串是： BCDEF BCDEFG BCPQRST