数据结构(本)形考作业答案

由天下分享时间：2024/12/4 21:31:58 加入收藏我要投稿点赞

精品

选择一项： A. （10，8，7） B. （10，8，6） C. （7，10，8） D. （7，8，10）

题目22

对一个栈顶指针为top的链栈进行入栈操作，通过指针变量p生成入栈结点，并给

该结点赋值a，则执行: p=(struct node *)malloc(sizeof(struct node);p->data=a;和（）。选择一项：

A. p->next=top;p=top; B. top->next=p;p=top; C. p->nex=top;top=p; D. top=top->next;pe=top;

题目23

头指针为head的带头结点的单向链表为空的判定条件是（）为真。选择一项： A. head==NULL B. head->next==NULL C. head->next!=NULL D. head->next!=NULL

题目24

设有一个对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数

组B中（数组下标从1开始），B数组共有55个元素,则该矩阵是（）阶的对称矩阵。选择一项： A. 20 B. 15 C. 10 D. 5

题目25

数组a经初始化char a[ ]=“English”;a[1]中存放的是（）。选择一项： A. \B. 字符n

感谢下载载

精品

C. \D. 字符E

二、填空题（每小题2分，共30分）题目26 循环队列队头指针在队尾指针回答题目27 下一个位置，队列是“满”状态。循环队列的引入，目的是为了克服回答题目28 假上溢。判断一个循环队列LU（最多元素为m）为空的条件是回答题目29 LU->front==LU->rear。题干向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行回答s->next=h;和h=s;操作。（结点的指针域为next）题目30 从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行x=h-题目31 在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为回答和r=s; r->next=s;（结点的指针域为next）题目32 在一个链队中，设f和r分别为队头和队尾指针，则删除一个结点的操作为回答f=f->next;。（结点的指针域为next）题目33 串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是回答字符题目34 。空串的长度是回答 0 ；空格串的长度是回答空格字符的感谢下载载

精品

。

题目35

设广义表L=((),())，则表头是______________，表尾是______________，L的长度是______________。

则表头是（），表尾是（（）），L的长度是2

题目36

广义表A（（a，b，c），（d，e，f））的表尾为回答((d,e,f))。

题目37

设有n阶对称矩阵A，用数组s进行压缩存储，当i≥j时，A的数组元素aij相应于数组s的数组元素的下标为回答

题目38

i(i-1)/2+j。（数组元素的下标从1开始）

对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的_______、_______和_______三项信息。答案：行下标、列下标和非零元素值

题目39

循环队列用a[0]，…，a[7]的一维数组存放队列元素，（采用少用一个元素的模式)，设front和rear分别为队头和队尾指针，且front和rear 的值分别为2和7，当前队列中的元素个数是回答5

题目40

。

循环队列的引入，目的是为了克服回答三、问答题（每小题5分，共20分）

题目41 完成满分5.00

假上溢。

题干

栈、队列和线性表的区别是什么？

答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。

队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。

题目42

设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是多少？

出队序列是e2,e4,e3,e6,e5,e1的过程：

感谢下载载

精品

（1）e1入栈（栈底到栈顶元素是e1）（2）e2入栈（栈底到栈顶元素是e1，e2）（3）e2出栈（栈底到栈顶元素是e1）（4）e3入栈（栈底到栈顶元素是e1，e3）（5）e4入栈（栈底到栈顶元素是e1，e3，e4）（6）e4出栈（栈底到栈顶元素是e1，e3）（7）e3出栈（栈底到栈顶元素是e1）（8）e5入栈（栈底到栈顶元素是e1，e5）（9）e6入栈（栈底到栈顶元素是e1，e5，e6）（10）e6出栈（栈底到栈顶元素是e1，e5）（11）e5出栈（栈底到栈顶元素是e1）（12）e1出栈（栈底到栈顶元素是空）

栈中最多时有3个元素，所以栈S的容量至少是3。

题目43

有5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先的次序有哪几个？

从题中可知，要使C第一个且D第二个出栈，应是A入栈，B入栈，C入栈，C出栈，D入栈。之后可以有以下几种情况：

（1）B出栈，A出栈，E入栈，E出栈，输出序列为：CDBAE。（2）B出栈，E入栈，E出栈，A 出栈，输出序列为CDBEA。（3）E入栈，E出栈，B出栈，A出栈，输出序列为CDEBA 所以可能的次序有：CDBAE，CDBEA，CDEBA

题目44

简述广义表和线性表的区别和联系。

广义表是线性表的的推广，它也是n（n>0）个元素a1，a2，…，ai，…，an的有限序列，其中ai或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的特殊情况，当ai都是原子时，广义表退化成线性表。

形考任务三

一、单项选择题（每小题2分，共32分）

题目1

假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）。选择一项： A. 17 B. 16 C. 15