数据库系统-数据结构复习题

数据结构期末综合练201312期末综合练数据结构在计算机内存中的表示是指( )。A．数据元间的关系 B．数据的结构 2.结构中的元间存在一对多的关系是 A．集 C．树形结构D3.对不结点的单向链表,判断是否为空的条件是（ headA．head==NULLB．head->next==NULLC．head->next= D．head表的第5个元素，则移动元素个数为（ p=q->next;p=p->next;B．p->next=q;p=p->next;C．p->next=q->next;q=p;D．p=p->next;q->next=p;在一个尾指针为rear的不结点的单循环链表中,插入一个s所指的结点,并作为第一 A．rear→next=s;s→next=rear→next 一个栈的进栈序列是1，2，3，4，5，则栈的不可能输出序列是（ 元素a，b，c,d按顺序依次进栈，则该栈的可能输出序列是（ 一个队列的入队序列是2，4，6，8，按该队列的输出序列使各元素依次入栈，该栈的可 A．x=top->data;top=top→next; C．top=top->next;x=top->data; D．top=top->next;x=data;frp,px,并入队的运算为（A.p->data=x;p->next=NULL;f->next=p;f=p;B．p->data=x;p->next=NULL;r->next=p;r=p;C．p->data=x;p->next=r;r=s;D．p->data=x;p-设有一个对称矩阵A，采用压缩的方式，将其下三角部分以行序为主序到一维B（1，B55（）阶的对称1a1,1 设有一个25阶的对称矩阵A，采用压缩的方式，将其下三角部分以行序为主序a7,6 1a1,1 B（153 1a1,1A．a8,5 以下程序段的结果是c的值为 chara[8]=“ ”,int*p=a,intc=0;char* inti,c=0; 一棵采用链式的二叉树中，共有n个指针域被有效使用（即指针域为非空。该二 C．n- i/2B．2i-1 D．i/2- A．n- 已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到 aaecbdf已知如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到 aaecbdfABCDEFGH已知如图3所示的一个图，若从顶点B出发，按广度优先法进行遍历，则可能得到的一ABCDEFGH（42376240392 2，37，40，42，62，92C．32，40，37，42，62，92（46385640784 （80,7,41,3946,47， 43时，经 B．3C．8 结构中的数据元素存在一对一的关系称为线性结构。而数据元素存在 的关系， 设有一个长度为25的顺序表，要删除前3个元素,则最少要移动元素的个数为（ 6．在双向链表中，要删除p所指的结点，可以先用语句（p->prior）->next=p->next；然 在双向链表中，要删除p所指的结点，其中所用的一条语句（p->prior）->next=p->next；的功能是：使P所指结点的直接前驱的右指针指向 设有一个头指针为head的单向链表，p指向链表中的某结点，若要使该链表成为单向循环链表，可用语句while(p->next!=NULL)p=p->next; ，向一个栈顶指针为top的链栈中插入一个p所指结点时用语句top=p；p-， top的链栈中取栈顶元素，用d 在一个链队中，设front和rear分别为队头和队尾指针，则s所指结点(数据域已赋值)的入队操作为s->next=NULL;. 和rear=s;循环链队列中，设front和rear分别为队头和队尾指针，(最多元素为MaxSize,),判断循环 设有n阶对称矩阵A，用一维数组s压缩A的下三角元素，s的下标从零开始，元素s[26]相应于A中的元素为 。(矩阵中的第1个元素是a1,1）对稀疏矩阵进行压缩,可采用三元组表，设a是稀疏矩阵A相应的三元组表类型（结构体类型）变量，a中的一个成员项是三元组类型的结构体数组data，按书中定义，若a.data[0].i=2;a.data[0].j=3;a.data[0].v=16;它提供的A数组的相关信息有 对稀疏矩阵进行压缩,可采用三元组表，设a是稀疏矩阵A相应的三元组表类型（结供的A矩阵的相关信息有 设有一棵深度为5的完全二叉树，该树共有20个结点,第五层上 （1层 层（根所在结点为第1层 2213547689 9 324.给定一组权重值，构造树， 1（1该树成为一棵二叉排序树，试给出a、b、c、d、e的大小关系。(1)说明什么是顶点活动网(AOV网)G3在图G中增加一条边，使图Gaadbc3（1）A3,A5,A7AAAAAAAAAA),.设待排序的记录序列存放在a[1],…a[n]a[0]a[1],…a[i-1]中。voidbinsort(NODEa[],intn) intfor（i=2；i<= while

x=a[i].key; m=(2) if(x<a[m].key) }for(k=i-1;k>=j+1;k-- }}回值是指向树结点的结构指针p（查找成功p指向查到的树结点不成功p指向为NULL） Bnode*left; Bnode*right;}Bnode*BSearch(Bnode*bt,int Bnode*p;if(bt== return(bt);while(p->key!=(2) {if(k<p- if(p==NULL)} } structnode*topvoidPush(ElemType{structnodep=(structnode*)malloc( (3)}}量，pa,（设链表中没有结点的数据域与结点a的数据域相同）,写出q=p;x=p-while（(1) q=p;p=p->next;{ }s- 期末综合练答1．B2．C3．A4．B5．D6．D7．B8．C9．A 11．B13．D14．B15．B16．A17．A18．A19．A20．D21．C22．D24．C25．C26．A27．B28．A6（p-7．P8．p-9．p-11．p本身14．front==rear16．A2，317．A11个非零元素，a8,5abcde1abcdeabdcadbcbd64645(1) (2)857748259136111111121112(2)4 2（3）3次4(3) n2（1）NULL3（1）sizeof(struct期末 一种逻辑结构在时 只要数据元素间的关系B．只能采用一种结C．可采用不同的结构D．只要数据元素的.对顺序表,以下叙述中正确的是 )C．数据元素不能随机 线性表在后,如果相关操作是:要求已知第i个结点的位置该结点的前驱结点， ）方式是不可行的。A．单链 C．单循环链表D．顺序设单向链表中,指针p指向结点A，若要删除A ) D.p->next=p A．B． 元素1，3，5，7按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列 C．6，2，4，8D．8，6，4，2 A．p=top->next;top=top→next; 在一个不结点的链队中，假设f和r分别为队头和队尾指针，则从该对列中删除一个结点并把结点的值保存在变量x中的运算为（ C．x=f→data；f=f→next;D．f=f→next;x=f→dataB（133 1a1,1 B．a10,8C．a9,2B（138 1a1,1 B（1a10,6B 1a1,1 在C语言中，分别“S”和‘s’，各需要占用 ）字节 trCmp“ABCd“ABCD 一棵有n个结点，采用链式的二叉树中，共有（ C．n- 已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到 aabecdf如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一 aabecdf（46,20,0,79534084,90110 D．20,30（5630,896685094,87,10 A．30，50,48，56，66，89，94,100,87B．50，30,48，56，66，89，94,87,100（756395，80，53，45，38，20， c.95,80,45,63,53,75,38,D．95,80,75,20,53,45,38, ）方式，能进行折半查找关键字有序的B．顺序C．关键字有序的顺序D．数数据元间的抽象关系称 度 。 为8,9,10,11,…,25，想要删除第8个元素，他的做法是从第25号元素开始,直到第9号元素依次向前移动1个位置,其结果新表中第9号元素的值为（ 设有一个长度为25825 先用语句q->next=p->next;（p->next）->prior=q；然后再用语句q->prior=p;和语句 指向q == (填两条语句, 。(next,数据域为在一个结点的链队中，设front和rear分别为队头和队尾指针，则删除一个结点的操作为p=front->next; =p->next;(结点的指针域为next, p为辅助用指针)14front和rear分别为队头和队尾指针，(MaxSize, 。设有n阶对称矩阵A，用一维数组s压缩A的下三角元素，s的下标从零开始，最后一个元素的下标为27，则n= 。(矩阵中的第1个元素是a1,1）对稀疏矩阵进行压缩,可采用三元组表，一个6行7列的稀疏矩阵A相应的三元组表共有8个元素,则矩阵A共有 一棵3度的树，其中3度结1个，2度结2个，1度结2个，则该树共有 一棵有8个权重值构造的数，共有个结点 1 2213547689 2213547689 以3，4，5，8，9，10作为叶结点的权，构造一棵树2（1）3（1）G131123456(1)如下的一棵树,1，2，…9AAAAAAAAAA0voidquicksort(NODEa[],intstart,intend NODEmidif(start>=end)while(i<j)

while(i<j&&a[j].key>mid.key)j--; }while(i<j&&(2) (3) }}quicksort(a,stat,i-1);quicksort(5) }a[1],a[2],…a[n]中的记录进行直接选择排序，完成 voidselsort(NODEa[],int{inti,j,k;NODEtemp;for(i=1;i<= {for(j=i+1;j<= if(a[j].key<a[k].key)(3) { }}}以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front、rear分别是 voidInQueue(ElemTypex){structnodep=(structnode*) p-p- rear= }4.设有一个头指针为head的不结点单向链表,且pq是指向链表中结点类型的指针,删去aq=p;x=p-while（q->next!=NULL）q=q- q=p;p=p->next;{ } 6．A7．A8．C 10．D 16．D17．C1