《数据结构C语言习题及解答》由会员分享，可在线阅读，更多相关《数据结构C语言习题及解答（59页珍藏版）》请在金锄头文库上搜索。
1、第二章 习题与解答一 判断题1线性表的逻辑顺序与存储顺序总是一致的。2顺序存储的线性表可以按序号随机存取。3顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 4线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。5在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。6在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。7线性表的链式存储结构优于顺序存储结构。8在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。9线性表的链式存储结构是用一组任意的存储单元
2、来存储线性表中数据元素的。10在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。二 单选题 (请从下列 A，B，C，D 选项中选择一项)1线性表是( ) 。(A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 2对顺序存储的线性表，设其长度为 n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ ）个元素。(A) n/2 (B) n+1/2 (C) n -1/2 (D) n 3线性表采用链式存储时，其地址( ) 。(A) 必须是连续的； (B) 部分地
3、址必须是连续的； (C) 一定是不连续的； (D) 连续与否均可以。 4用链表表示线性表的优点是（ ） 。(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同5 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。(A)单链表(B)双链表(C)单循环链表(D)带头结点的双循环链表6 循环链表的主要优点是( ) 。(A)不在需要头指针了(B)已知某个结点的位置后，能够容易找到他的直接前趋(C)在进行插入、删除运算时，能更好的保证链表不断开(D)从表中的任意结点出发都能扫描到整个链表7
4、下面关于线性表的叙述错误的是( )。(A) 线性表采用顺序存储，必须占用一片地址连续的单元；(B) 线性表采用顺序存储，便于进行插入和删除操作；(C) 线性表采用链式存储，不必占用一片地址连续的单元；(D) 线性表采用链式存储，不便于进行插入和删除操作；8 单链表中，增加一个头结点的目的是为了（） 。(A) 使单链表至少有一个结点 (B)标识表结点中首结点的位置（C）方便运算的实现 (D) 说明单链表是线性表的链式存储9 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。(A) 单链表 (B) 仅有头指针的单循环链表 (C) 双链表
5、(D) 仅有尾指针的单循环链表10 若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素，则采用（ ）存储方式最节省运算时间（ ） 。(A) 单链表 (B) 顺序表 (C) 双链表 (D) 单循环链表三 填空题1带头结点的单链表 H 为空的条件是 _。1 非空单循环链表 L 中*p 是尾结点的条件是_。3在一个单链表中 p 所指结点之后插入一个由指针 f 所指结点，应执行 s-next=_;和 p-next=_的操作。4在一个单链表中 p 所指结点之前插入一个由指针 f 所指结点，可执行以下操作：s-next=_;p-next=s;t=p-data;p-data=_;s-da
6、ta=_;5在顺序表中做插入操作时首先检查_。四 算法设计题1 设线性表存放在向量 Aarrsize的前 elenum 个分量中，且递增有序。试写一算法，将 x 插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。2 已知一顺序表 A，其元素值非递减有序排列，编写一个函数删除顺序表中多余的值相同的元素。3 编写一个函数，从一给定的顺序表 A 中删除值在 xy(x0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限 m，从第一个人开始顺时针方向自 1 起顺序报数，报到 m 是停止报数，报 m 的人出列，将他的密码作为新的 m值，从他的下一
7、个人开始重新从 1 报数。如此下去，直到所有人全部出列为止。令 n 最大值取 30。要求设计一个程序模拟此过程，求出出列编号序列。源程序代码：（在 Tubro C 2.0 测试通过）#include #include struct nodeint number; /* 人的序号 */int cipher; /* 密码 */struct node *next; /* 指向下一个节点的指针 */;coef exp nextstruct node *CreatList(int num) /* 建立循环链表 */int i;struct node *ptr1,*head;if(ptr1=(struct
8、 node *)malloc(sizeof(struct node)=NULL)perror(malloc);return ptr1;head=ptr1;ptr1-next=head;for(i=1;inext=(struct node *)malloc(sizeof(struct node)=NULL)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;ran
9、domize();head=CreatList(n);for(i=1;inumber=i;head-cipher=rand();head=head-next;m=rand(); /* m 取随机数 */i=0; /* 因为我没办法删除 head 指向的节点，只会删除 head 的下一节点，所以只能从0 数起。*/while(head-next!=head) /* 当剩下最后一个人时，退出循环 */if(i=m)ptr=head-next; /* ptr 记录数到 m 的那个人的位置 */printf(number:%dn,ptr-number);printf(cipher:%dn,ptr-ci
10、pher);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); /* 让最后一个人也出列 */第三
11、章 习题一、基本题1填空：线性表、栈和队列都是_结构，可以在线性表的_位置插入和删除元素，对于栈只能在_位置插入和删除元素，对于队只能在_位置插入和_位置删除元素。2. 栈和队列数据结构的特点，什么情况下用到栈，什么情况下用到队列？3设有编号为 1，2，3，4 的四辆车，顺序进入一个栈式结构的站台，试写出这四辆车开出车站的所有可能的顺序（每辆车可能入站，可能不入站，时间也可能不等） 。4试证明：若借助栈由输入序列 1，2， ，n 得到输出序列为 p1p2pn (它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着 in0+=1+n2+(m-1)nM6.5 一个深度为 h 的满
12、k 叉树有如下性质：第 h 层上的结点都是叶子结点，其余各层上每个结点都有 k 棵非空子树。如果按层次顺序（同层自左至右）从未有过开始对全部结点编号，问：（1） 各层的结点数目是多少？（2） 编号为 i 的结点的双亲结点（若存在）的编号是多少？（3） 编号为 i 的结点的第 j 个孩子结点（若存在）的编号是多少？（4） 编号为 i 的结点有右兄弟的条件是什么？其右兄弟的编号是多少？解：（1） Ki-1（2）（3） Ki+j-1（4） (i-1)MOD Klchild,Visit); /*遍历左子树*/Visit(T-data); /*通过函数指针调用它所指的函数来访问结点*/Inorder(T
13、-rchild,Visit); /*遍历右子树*/其中 Visit 是一个函数指针，它指向形如 void f（DdataType x）的函数。因此我们可以将访问结点的操作写在函数 f 中，通过调用语句 Inorder（root，f）将 f 的地址传递给 Visit，来执行遍历操作。请写一个打印结点的数据的函数，通过调用上述算法来完成书中 6.3 节的中序遍历。解：#include“stdio.h”#define Null 0 typedef char DataType;typedef struct nodeDataType data;Struct node lchild,rchild;BinT
14、ree;BinTree *root;BinTree *Q100;BinTree CreateBinTree() /*建立二叉树*/ char ch;int front,rear;BinTree root,s;Root=Null;front=1;rear=0;ch=getchar();while(ch!=#)s=Null;if(ch!=)s=(BinTree*)malloc(sizeof(BinTree);s-data=ch;s-lchild=Null;s-rchild=Null;rear +;Qrear=s;if(rear=1) root=s;elseif(s&Qfront)if(rear%2
15、=0) Qfront-lchild=s;elseQfront-rchild=s;if(rear%2=1) front+;ch=getchar();return root;main()root=CreateBinTree();Inorder(root); 中序遍历法之一Inorder(BinTree *t)if(t)Inorder(t-lchild);Visit(t-data);Inorder(t-rchild);Vist(int i)printf(“%c”,i); 中序遍历法之二Inorder(BinTree *t)if(t)Inorder(t-lchild);printf(“%c”,t-data);Inorder(t-rchild);6.23 以二叉链表为存储结构，分别写出求二叉树结点总数及叶子总数的算法。解： 计算结点总
