【答案】：错误。
线性表的每个结点可以是简单类型，也可以是一个复杂类型。 而链表的每个结点因为是结构类型，所以它是一个复杂类型。
8．对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表. 【答案】：正确。
9．在表结构中最常用的是线性表，栈和队列不太常用。 【答案】：错误。 线性表、栈和队列都是最常用的线性结构。
四、问答题
1．试比较顺序存储结构和链式存储结构的优缺点。
【答案】： 顺序存储结构的优点是：能实现随机存取；存储密度大，存储空间利用率高。缺点是：插入元素时会有表溢出的情况；在插入和删除元素时将要引起大量元素的移动。 链式存储结构的优点是：插入元素时不会有表溢出的情况；在插入和删除元素时不需要移动任何元素，只需改变指针域中的指针值就可以了。缺点是：只能实现顺序存取；存储密度小，存储空间利用率不高。
2． 写出一个计算单链表中结点个数的算法，其中指针p指向该链表的第一个结点。 【分析】：根据单链表的特性，从单链表第一个结点开始计数，只要是非空结点，计数器加1，直到所有结点都走过一遍。
【答案】：
typedef struct snode{char data； struct snode *link；} NODE； int length(NODE *p){ NODE *q； int i；
q=p； i=0； /* 初始化 */
while (q!= NULL){ i++； q=q->link； } return (i)； }
3． 给定一个n项元素的线性表V，写一个算法，将元素排列的次序颠倒过来，要求仍占用
原来的空间，并且用顺序表和单链表两种方法表示。 【分析】：将V[1]与V[n]交换，V[2]与V[n-1]交换，??，V[n/2]与V[n/2+1]交换. 【答案】：顺序表结构下的实现： #define M 1000 int v[M]； int n；
void invert( ){ int temp；
for(i=0；i<=n/2；i++){ temp=v[i]； }
v[i]=v[n-i-1]； v[n-i-1]=temp； }
6
【分析】：依次从原单链表的头部删除一个结点，在插入到另一个从空链表开始的单链表的头部。 【答案】：单链表结构下的实现：
typedef struct snode{char data； struct snode *link；} NODE； void invert(NODE *head ){ NODE *p，*u； p=NULL;
while (head!=NULL){
u=head； /*在头部删除一个结点 */ head=head->link；
u->link=p；/*将删除的结点插入到另一个链表中 */
p=u； }
head=p；/* 新链表的头指针 */ }
4．试设计实现在单链表中删除值相同的多余结点的算法。 【答案】：
typedef struct snode{char data； struct snode *link；} NODE； void purge_lklist(NODE *head){
NODE *p，*q，*r；
p=head->link；/* p指向当前检查结点的位置，先将其初始化 */ if(p==NULL) return；/* 空表返回 */
while(p->linkt!=NULL){ /* 当前结点不是尾结点 */ q=p；
while(q->link!=NULL) /* 删除值与p所指结点的值相同的结点 */ if(q->link->data==p->data){ /* 若有值相同的结点*q */
r=q->link；
q->link = q->link->link； /* 删除多余结点 */ free(r )； }
else q=q->link；/* 找下一个可以的多余结点 */
p=p->link； } /* 更新检查结点 */ }
5．描述以下三个概念的区别：头指针、头结点、首元元素结点。 【答案】：头指针：是指向单链表的第一个结点的指针。
头结点：在链表的首元元素结点之前附设的一个结点。 首元元素结点：是指用于存储线性表中第一个数据的结点。
6．写出计算线性链表长度的算法。 【分析】：：根据单链表的特性，从单链表第一个结点开始访问，只要是非空结点，计数一次，直到所有结点访问一遍。 【答案】：
typedef struct snode{char data； struct snode *link；} NODE；
7
int length(NODE *head){ NODE *p； int i；
p=head； i=0； /*初始化 */ while (p!=NULL){ i++； p = p->link； } return (i)； }
7．设有一个线性链表，其结点为正整数，且按值从小到大链接。试写出一个算法，将此线性链表分解成两个线性链表，其中一个链表中的结点值均为奇数，而另一个链表中的结点值均为偶数，且这两个链表均按值从小到大链接。
【分析】：在链表head中依次取元素(s->data)，若取出的元素是奇数，把它插入到奇数链表ahead中，若取出的元素是偶数，把它插入到偶数链表bhead中，继续取下一个元素，直到链表的尾部，头指针ahead和bhead分别指向奇数链表和偶数链表。 【答案】：
typedef struct snode{int data； struct snode *link；} NODE； void examp7(NODE *head，*ahead，*bhead){ NODE *p，*q，*s；
ahead=(NODE *)malloc(sizeof(NODE))；/* 建立奇数链表的头结点 */ p=ahead；， /* 工作指针p初始化。*/
bhead=(NODE *)malloc(sizeof(NODE))；/* 建立偶数链表的头结点 */
q=bhead； /*工作指针q初始化。*/
s= head->link； free(head)；/* s为原表中的工作指针，释放原表中的头结点 */ while (s!= NULL){
if( s->data % 2==0) /*是偶数 */ { q->link = s ； q = q->link ；} else / * 是奇数 * / { p->link = s ； p = p->link； } s = s->link ； /* 取下一个结点 */ }
p->link = NULL； /* 置奇数表的表尾 */ q->link = NULL； /* 置偶数表的表尾 */ }
8．假设有一个循环单链表的长度大于1，且表中既无头结点也无头指针。已知S为指向链表中某结点的指针，试编写算法，在链表中删除S指针所指结点的前驱结点。 【分析】：：设置一个指针p，指向S结点的前驱结点的前驱结点。 【答案】：
typedef struct snode{char data； struct snode *link；} NODE； NODE *s；
void deleteprior( ){
NODE *p， *q； p = s；
while(p->link->link!=s)p=p->link；/*让p指向s结点的前驱结点的前驱结点 */
8
q=p->link； /* q指向被删除结点 */ p->link = q->link； /* 删除 */ free(q)； }
9．已知指针ha和hb分别指向两个单链表的头结点，且头结点的数据域中存放链表的长度，试写出一个算法将这两个链表连接在一起，并要求算法以尽可能短的时间内完成运算。 【分析】：：令表hb的首元结点连在表ha中的最后一个结点之后，首先想将工作指针p从ha的首元结点开始遍历到表ha中的最后一个结点，hc指向连接后的链表的头结点。
【答案】：
typedef struct snode{char data； struct snode *link；} NODE；
NODE *ha，*hb，*hc； void example9( ){ NODE *p； int i；
hc = ha ； /* hc指向连接后的链表的头结点 */ p = ha->link；
i=1； /* 用于表ha中结点的计数器 */
while(i
hc->data = ha->data + hb->data； /* 连接后的链表的长度 */ }
10．对于下面的每一步，画出栈元素和栈顶指针示意图。
（1）栈空；（2）在栈中入栈一个元素A；（3）在栈中入栈一个元素B； （4）出栈中一个元素；（5）在栈中入栈一个元素C； （6）出栈中一个元素；（7）出栈中一个元素； 【答案】： A B A A C A A （6）
（7）
（1） （2） （3） （4） （5）
11．设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。 【答案】： 1，2，3，4； 4，3，2； 2，1，3，4； 4，3，1；
1，2，4，3； 2，1，3，3；
1，3，1，4； 2，3，1，4； 3，4，2，1；
1，3，4，2； 2，3，4，1； 4，3，2，1；
1，2，
3，2，1，4； 3，2，4，1；
12．说明栈和队列的异同点。
9
【答案】：
相同点：栈和队列都是线性表结构； 不同点：栈是限定在线性表的一端进行插入和删除的操作；而队列的插入和删除在线性表的两端进行；
13．顺序队的“假溢出”是怎样产生的？如何知道循环队是空还是满？ 【答案】：
队列的尾指针已经到了数组的上界，此时如果还要执行入队运算，就要发生“上溢”，但是数组中还有空位置，这种现象称为“假溢出”。 在循环队中， 当rear==front时，表示队空；当 (rear+1)%M= =front时，表示队满。
14．设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 （1）front = 11， rear=19；（2）front = 19， rear = 11；问在这两种情况下，循环队
列中的各有多少个元素？ 【答案】： （1）：8个 ； （2）：32 ；
15．假设一数组squ[m]存放循环队列的元素。若要使m个分量都得到利用，则需要另一个标志tag，以tag为0或1来区分队尾指针和队头指针值相同时队列的状态是“空”还是“满”。试编写与此结构相应的入队和出队的算法。 【答案】：
#define M 100
int squ[M]，front，rear，tag；/* 队列中加一个标志域tag */ int addque(int x) { /* 入队运算 */ if ((tag==1)&&(front==rear))
{ printf(“full queuer!\\n”)； return (-1) ； } else
{ rear = (rear+1)%M； squ[rear] = x；
if (rear==front) tag=1 ； /* 如果插入后队列满，则置标志 */
} }
int delque( ) { /* 出队运算 */
if( tag==0) &&(front==rear))
{printf (“empty queuer !\\n”)； return(-1)； } else
{ front = （front+1}% M；
if(front==rear) tag=0；/* 如果删除后队列空，则置标志 */ return (squ[front])； } }
16．假设以带头结点的循环单链表表示队列，并且只设一个指针指向队尾元素结点，不设头
10
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库自考 2365计算机软件基础（二）课后 习题(2)在线全文阅读。
相关推荐：