sokaoti.com
2017年电大本科《数据结构（本）》期末复习试题及答案
A.p->next = =NULL
B.p= =NULL
C.p= =head
D.p->next= =head
●试题三
阅读下列说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
本题给出四个函数，它们的功能分别是：
1.int push(PNODE *top，int e)是进栈函数，形参top是栈顶指针的指针，形参e是入栈元素。
2.int pop(PNODE *top，int *e)是出栈函数，形参top是栈顶指针的指针，形参e作为返回出栈元素使用。
3.int enQueue(PNODE *tail，int e)是入队函数，形参tail是队尾指针的指针，形参e是入队元素。
4.int deQueue(PNODE *tail，int *e)是出队函数，形参tail是队尾指针的指针，形参e作为返回出队元素使用。
以上四个函数中，返回值为0表示操作成功，返回值为-1表示操作失败。
栈是用链表实现的；队是用带有辅助结点(头结点)的单向循环链表实现的。两种链表的结点类型均为：
typedef struct node{
int value；
struct node *next；
}NODE，*PNODE；
【函数1】
int push(PNODE *top，int e)
{
PNODE p=(PNODE)malloc (sizeof(NODE))；
if (!p) return-1；
p-> value =e；
(1) ；.
*top=p；
return 0；
}
【函数2】
int pop (PNODE *top，int *e)
{
PNODE p=*top；
if(p==NULL)return-1；
*e=p->value；
(2) ；
free(p)；
return 0；
}
【函数3】
int enQueue (PNODE *tail，int e)
{PNODE p，t；
t=*tail；
p=(PNODE)malloc(sizeof(NODE))；
if(!p)return-l；
p->value=e；
p->next=t->next；
(3) ；
*tail=p；
return 0；
}
【函数4】
int deQueue(PNODE *tail，int *e)
{PNODE p，q；
if((*tail)->next==*tail)return -1；
p=(*tail)->next；
q=p->next；
*e=q->value；
(4) =q->next；
if(*tail==q) (5) ；
free(q)；
return 0；
}
●试题三
【答案】(1)p->next=*top(2)*top=p->next或*top=(*top)->next
(3)t->next=p或(*tail)->next=p(4)p->next或(*tail)->next->next
(5)*tail=p或*tail=(*tail)->next
【解析】(1)插入结点p后，p应当指向插入前头结点，所以填入p->next=*top。(2)出栈后，头指针应指向它的下一结点，所以填入*top=p->next或*top=(*top)->next。(3)入队时，需要将结点插入队尾，所以应当填入(*tail)->next=p或t->next=p(t也指向尾结点)。(4)出队时，需要删除队头结点，通过(*tail)->next可以得到对队头结点的引用。(4)处是正常删除队头结点的情况，空格处应填入头结点指向下一结点的指针，即p->next或(*tail)->next->next。(5)处是需要考虑的特殊情况，即队列中最后一个元素出队后，要更新队尾指针，即填入*tail=p或*tail=(*tail)->next。
A.p->next=top;top=p;
B.top->next=p;
C.p->next=top->next;top=top->next;
D.p->next=top->next;top->next=p;
A.p==head
B.p==NULL
C.p->next==head
D.p->next==NULL
2017年电大本科数据结构（本）期末复习试题及答案一、单项选择题1栈和队列的共同特点是（）。A.元素都可以随机进出B.都是先进先出C.都是先进后出D.都是操作受限的线性结构2.数据的存储结构包括数据元素的表示和（）。A.数据处理的方法B.数据元素间的关系的表示C.相关算法D.数据元素的类型3对一个栈顶指针为top的链栈进行入栈操作，通过指针变量p生成入栈结点，则执行：p=(structnode*)malloc(sizeof(structnode);p-data=a;和（）。A.top-next=p;p=top;B.p-nex=top;top=p;C.top=top-next;p=top;D.p-next=top;p=top;4树状结构中数据元素的位置之间存在（）的关系。A每一个元素都有一个直接前驱和一个直接后继B一对一C多对多D一对多5设头指针为head的非空的单向链表,指针p指向尾结点,则通过以下操作()可使其成为单向循环链表。Ap-next=NULL;Bhead=p;Cp-next=head;Dp=head;6设有一个长度为26的顺序表，要插入一个元素,并使它成为新表的第6个元素,需移动元素的个数为（）。A21B22C20D197一种逻辑结构（）。A只能有唯一的存储结构B可以有不同的存储结构C与存储该逻辑结构的计算机相关D是指某一种数据元素的性质8头指针为head的带头结点的单向循环链表，p所指向尾结点，要使该链表成为不带头结点的单向循环链表,可执行head=head-nex;和（）。Ap=head-nextBhead-next=pChead-next=p-nextDp-next=head;9把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。A存储结构B逻辑结构C数据元素的存储D.给数据元素分配存储空间10元素111，113，115，117按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。A117，115，113，111B111，113，115，117C117，115，111，113D113，111，117，11511图状结构中数据元素的位置之间存在（）的关系。A一对一B一对多C多对多D每一个元素都有一个且只有一个直接前驱和一个直接后继12以下说法正确的是（）。A栈的特点是先进先出B栈的特点是先进后出C队列的特点是先进后出D.栈和队列的特点都是后进后出13一个单链表中,在p所指结点之后插入一个s所指的结点时，可执行:s-next=p-next;和（）。As=p-next;Bp-next=s-next;Cp=s-next;Dp-next=s;14.设有一个20阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵元素a6,2在一维数组B中的下标是（）。A21B28C17D2315元素12，14，16，18顺序依次进栈，则该栈的不可能输出序列是（）。（进栈出栈可以交替进行）。A18，16，14，12B12，14，16，18D14，12，18，16D18，16，12，1416设有串p1=”ABADF”,P2=”ABAFD”，P3=”ABADFA”,P4=”ABAF”,以下四个串中最大的是()。Ap3Bp2Cp1Dp417设有一个30阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（）。A41B32C18D3818.数组a经初始化chara=“English”;a7中存放的是（）。A.字符串的结束符B.字符hC.hD.变量h19设有一个长度为32的顺序表，要删除第8个元素需移动元素的个数为（）。A15B22C14D2420.设主串为“ABcCDABcdEFaBc”，以下模式串能与主串成功匹配的是（）。A.BcdB.BCdC.ABCD.Abc21.在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（）。A2iB2i-1C2i+1D2i+222在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为（）。A2i+1B2i-1C2iD2i+223一棵具有16个结点的完全二叉树，共有（）层。(设根结点在第一层)A7B6C4D524如图1所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。AabecdfBaebcfdCaecbdfDaedfcb25如图2所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。AabecdfgBacfebgdCaebcfgdDaedfcgb26线性表以（）方式存储，能进行折半查找。A链接B顺序C关键字有序的顺序D二叉树27.字符串“DABcdabcd321ABC”的子串是()。A.“cd32”B.“ABcD”C.“aBcd”D.“321a”28一棵具有38个结点的完全二叉树，最后一层有（）个结点。A7B5C6D829如图3所示，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。AabcdfgeBabcdfegCacbfedgDabcfgde30.下图4的拓扑序列是()。A52346B23645C56234D.23564二、填空题1.对稀疏矩阵进行压缩存储,可采用三元组表，一个有10行的稀疏矩阵A共有97个零元素，其相应的三元组表共有3个元素。该矩阵A有列。2结构中的数据元素存在多对多的关系称为_结构。3在单向链表中，q指向p所指结点的直接后继结点，要删除q所指结点，可以用操作_=q-next;。4.n个元素进行冒泡法排序，第j趟冒泡要进行_次元素间的比较。5.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行下标、列下标和_三项信息。6中序遍历_树可得到一个有序序列。7.队列的操作特点是后进_。8.待排序的序列为8,3,4,1,2,5,9,采用直接选择排序算法,当进行了两趟选择后,结果序列为()。9n个元素进行冒泡法排序，通常需要进行_趟冒泡。10广义表(a,b),d,e,(i,j),k)的长度是_。11中序遍历二叉排序树可得到一个_的序列。12.广义表的(c，a,(a,b),d,e,(i,j),k)深度是_。13.广义表(c,a,(a,b),d,e,(i,j),k)的长度是_。14.对稀疏矩阵进行压缩存储,可采用三元组表，一个有10行10列的稀疏矩阵A共有95个零元素，其相应的三元组表共有个元素。15.广义表的(c,a,(a,b),d,e,(i,j),k)深度是_。16在对一组记录(50,49,97,22,16,73,65,47,88)进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较_次。17.循环队列在规定少用一个存储空间的情况下，队空的判定条件为_。18.一棵有5个叶结点的哈夫曼树,该树中总共有_个结点。19.c语言中,字符串“E”存储时占个字节。20.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有_个结点。（根所在结点为第1层）。21一棵二叉树中有n个非叶
A.p->next=top;p=top;
B.top->next=p;p=top;
C.p->nex=top;top=p;
D.top=top->next;pe=top;
阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。
[说明]
用链式存储结构实现的栈称为链栈。若链栈元素的数据类型为datatype，以LinkStack记链栈结构，其类型定义为：
typedef struct node
{ datatype data；
stmct node * next;
} StackNode, * LinkStack;
由于栈的主要操作都是在栈顶进行的，因此我们把链表的头部作为栈顶。设top为栈顶指针，即：LinkStack top。
下面各函数的功能说明如下：
(1)LinkStack Init_LinkStack()：建立并返回空的链栈；
(2)int Empty_LinkStack(LinkStack top)：判断top所指链栈是否空；
(3)LinkStack Push_LinkStack(LinkStacktop，datatypex)：将数据x压人top所指链栈的栈顶，返回新栈指针；
(4)LinkStack Pop_LinkStack (LinkStacktop, datatype*x)：弹出top所指链栈的栈顶元素x，返回新栈指针。
[函数]
LinkStaek Init_LinkStack( )
{ returnNULL;
int Empty_LinkStack ( LinkStaek top)
if(top = = NULL) return 1;
else return 0;
LinkStaek Push_LinkStaek( LinkStaektop, datatype X)
{ StaekNode *s;
s=malloc (sizeof(StaekNode) );
(1)= x;
(2)= top;
(3);
return top;
}
LinkStaek Pop_LinkStack (LinkStacktop, datatype * x)
{ StaekNode *p;
if(top = = NULL) return NULL;
else{
* x =(4);
p = top;
(5);
free (p);
return top;
}
}
(1)s-＞data (2)s-＞next (3)top=s (4)top-＞data (5)top=top-＞next 解析：(1)～(3)：LinkStack Push_LinkStack(Link- Stacktop，datmype x)函数的功能是将x压入栈顶，因此首先为其创建一个节点s，使s-＞data等于x，使s-＞ next指向原来的栈顶top，最后将，作为新栈的栈顶并返回。
(4)～(5)：LinkStack Pop_LinkStaek(LinkStacktop， datatype*x)的功能是弹出原栈顶元素，返回这个元素以及新栈的指针。当原链栈不空时，取出栈顶元素top -＞data赋给参量*x作为返回值，将top-＞next更新为新栈的栈顶，并且释放原来top节点的空间。
阅读以下说明，回答问题1～4，将解答填入对应的解答栏内。
[说明] 假设二叉树采用连接存储结构进行存储，root 指向根接点，p 所指结点为任一给定的结点，编写一个求从根结点到p所指结点之间路径的函数。
void path (root, p)
btree * root, * p;
{
Btree *stack[m0], *s;
int tag[m0], top =0, i, find =0;
s =root;
do
{
while (s ! = NULL)
{
stack [top] = s;
tag[top] =0;
((1))
}
if (top ＞0)
{
((2))
if (tag[top] = =1)
{
if((3))
{
for (i=1; i＜ =top; i+ + printf ("%d" ,stack[i]- ＞data);
find=1;
}
else top - -;
}
if((4))
{
p=p- ＞right;
((5))
}
}
} while (find ｜｜ (s! = NULL && top ! =0));
}
(1)s=s->left； (2)s=stack [top]； (3)(s==p) (4)(top>0 && ! find) (5)tag [top]=1 解析：本题采用非递归后序遍历数root，当后序遍历访问到p所指结点时，此时stack中所有的结点均为P所指结点的祖先，由这些祖先便构成了一条从根结点到p所指结点之间的路径。
阅读下列说明和C代码，将应填入(n)处的字句写在对应栏内。
【说明】
本题给出四个函数，它们的功能分别是：
1．int push(PNODE*top，int e)是进栈函数，形参top是栈顶指针的指针，形参e是入栈元素。
2．int pop(PNODE*top，int*e)是出栈函数，形参top是栈顶指针的指针，形参e作为返回出栈元素使用。
3．int enQueue(PNODE*tail，int e)是入队函数，形参tail是队尾指针的指针，形参e是入队元素。
4．int deQueue(PNODE*tail，int*e)是出队函数，形参tail是队尾指针的指针，形参e作为返回出队元素使用。
以上四个函数中，返回值为。表示操作成功，返回值为-1表示操作失败。
栈是用链表实现的；队是用带有辅助结点(头结点)的单向循环链表实现的。两种链表的结点类型均为：
typedef struct node {
int value;
struct node * next;
} NODE, * PNODE;
【函数1】
int push(PNOOE * top,int e)
{
PNODE p = (PNODE) malloc (sizeof (NODE));
if (! p) return-1;
p-＞value=e;
(1);
*top=p;
return 0;
}
【函数2】
int pop (PNODE * top,int * e)
{
PNODE p = * top;
if(p == NULL) return-1;
* e = p-＞value;
(2);
free(p);
return 0;
}
【函数3】
int enQueue (PNODE * tail,int e)
{ PNODE p,t;
t= *tail;
p = (PNODE) malloc(sizeof(NODE));
if(!p) return-1;
p-＞value=e;
p-＞next=t-＞next;
(3);
* tail = p;
return 0;
}
【函数4】
int deQueue(PNODE * tail,int * e)
{ PNODE p,q;
if(( * tail)-＞next == * tail) return-1;
p= (* tail)-＞next;
q = p -＞next;
* e =q -＞value;
(4)=q-＞next;
if(,tail==q) (5);
free(q);
return 0;
}
(1)p-＞next=*top (2)*top=p-＞next或* top=(*top)-＞next (3)t-＞next=p或(*tail)-＞next=p (4)p-＞next或(*tail)-＞next-＞next (5)*tail=p或*tail=(*tail)-＞next 解析：(1)插入结点p后，p应当指向插入前头结点，所以填入p -＞next=*top。(2)出栈后，头指针应指向它的下一结点，所以填入 *top=p-＞next或*top=(*top)-＞next。(3)入队时，需要将结点插入队尾，所以应当填入(*tail)-＞next=p或t-＞next=p(t也指向尾结点)。(4)出队时，需要删除队头结点，通过(*tail)-＞next可以得到对队头结点的引用。(4)处是正常删除队头结点的情况，空格处应填入头结点指向下一结点的指针，即p-＞next或(*tail)-＞next-＞next。(5)处是需要考虑的特殊情况，即队列中最后一个元素出队后，要更新队尾指针，即填入*tail=p或*tail=(*tail)-＞next。
阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。
[说明]
已知一棵二叉树用二叉链表存储，t指向根结点，p指向树中任一结点。下列算法为输出从t到P之间路径上的结点。
[C程序]
define Maxsize 1000
typedef struct node{
TelemType data;
struct node*1child,*rchild;
}BiNode,*BiTree;
void Path(BiTree t,BiNode*P)
{ BiTree*stack[Maxsize],*stackl[Maxsize],*q;
int tag[Maxsize],top=0,topl;
q=t;
/*通过先序遍历发现P*/
do(while(q!=NULL && q!=p)
/*扫描左孩子，且相应的结点不为P*/
{ (1);
stack[top]=q;
tag[top]=0;
(2);
}
if(top＞0)
{ if(stack[top]==P) break; /*找到P，栈底到栈顶为t到P*/
if(tag[top]==1)top--;
else{q=stack[top];
q=q-＞rchild;
tag[top]=1;
}
}
} (3);
top--; topl=0;
while(top＞0){
q=stack[top]; /*反向打印准备*/
topl++;
(4);
top--;
}
while((5)){ /*打印栈的内容*/
q=stackl[topl];
printf(q-＞data);
topl--;
}
}
(1) top++ (2) q=q-＞1child (3) while(top＞0) (4) stackl[top1]=q (5) top1＞0 解析：本题本质上是对二叉树的先序遍历进行考核，但不是简单地进行先序遍历，而是仅遍历从根结点到给定的结点p为止。本题采用非递归算法来实现，其主要思想是：①初始化栈：②根结点进栈，栈不空则循环执行以下步骤直到发现结点p；③当前结点不为空且不为P进栈；④栈顶为p，则结束，否则转③；⑤若右子树访问过，则栈顶的右孩子为当前结点，转③。
扫描左孩子，当相应的结点不为P时进栈，所以(1)填“top++”，(2)填“q=q-＞1child”。在栈不为空时则一直在do while循环中查找，因此(3)填“while(top＞0)”。在进行反向打印准备时，读取stack[top]的信息放到stackl[top]中，即(4)填“stackl[top1]=q”。打印栈中所有内容，所以(5)填“top1＞0”。