山开数据结构期末复习题

2023学年数据结构复习题一、单选题1、一组记录的关键字序列为（25，48，16，35，79，82，23，40，36，72），其中，含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（

）。A、16，25，35，48，23，40，79，82，36，72B、16，25，35，48，79，82，23，36，40，72C、16，25，48，35，79，82，23，36，40，72D、16，25，35，48，79，23，36，40，82，72正确答案：A2、顺序查找法与二分查找法对存储结构的要求是（

）。A、顺序查找与二分查找均只是适用于顺序表B、顺序查找与二分查找均既适用于顺序表，也适用于链表C、顺序查找只是适用于顺序表D、二分查找适用于顺序表正确答案：D3、已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（

）。A、V1V2V4V8V3V5V6V7B、V1V2V4V5V8V3V6V7C、V1V2V4V8V5V3V6V7D、V1V3V6V7V2V4V5V8正确答案：C4、设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（

）。A、abdecB、debacC、debcaD、abedc正确答案：C5、在图的存储结构表示中，表示形式唯一的是（

）。A、nB、n+1C、n-1D、n/2正确答案：C6、在正常情况下，直接插入排序的时间复杂度为（

）。A、O(log2n)B、

O(n)C、

O(nlog2n)D、

O(n2)正确答案：D7、将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（

）。A、33B、34C、35D、36正确答案：B8、以下陈述中正确的是（

）。A、串是一种特殊的线性表B、串的长度必须大于零C、串中元素只能是字母D、空串就是空白串正确答案：A9、设一棵哈夫曼树共有n个叶结点，则该树有（

）个非叶结点。A、nB、n-1C、n+1D、2n正确答案：B10、利用n个值作为叶结点的权生成的哈夫曼树中共包含有(

)个结点。A、nB、n+1C、2*nD、2*n-1正确答案：D11、数据结构中，与所使用的计算机无关的是数据的（

）。A、存储结构B、物理结构C、逻辑结构D、物理和存储结构正确答案：C12、下列的叙述中，不属于算法特性的是（

）。A、有穷性B、输入性C、可行性D、可读性正确答案：D13、设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（

）。A、n-i+1B、n-iC、n-i-1D、i正确答案：B14、在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（

）。A、p=q->nextB、p->next=qC、p->next=qànextD、q->next=NULL正确答案：C15、链表不具有的特点是（

）。A、可随机访问任一元素B、插入删除不需要移动元素C、不必事先估计存储空间D、所需空间与线性表长度成正比正确答案：A16、在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（

）。A、f->next=s;f=s;B、r->next=s;r=s;C、s->next=r;r=s;D、s->next=f;f=s;正确答案：B17、一个队列的入队序列是1，2，3，4。则队列的输出序列是（

）。A、4，3，2，1B、1，2，3，4C、1，4，3，2D、3，2，4，1正确答案：B18、在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（

）。A、top->next=p;B、p->next=top->next;top->next=p;C、p->next=top;top=p;D、p->next=top->next;top=top->next;正确答案：C19、判断一个循环队列Q（最多元素为m0）为空的条件是（

）。A、Q->front==Q->rearB、Q->front!=Q->rearC、Q->front==(Q->rear+1)%m0D、Q->front!=(Q->rear+1)%m0正确答案：A20、一个递归算法必须包括（

）。A、递归部分B、终止条件和递归部分C、迭代部分D、终止条件和迭代部分正确答案：B21、设有两个串p和q，其中q是p的子串，q在p中首次出现的位置的算法称为（

）。A、求子串B、连接C、匹配D、求串长正确答案：C22、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（

）。A、4B、5C、6D、7正确答案：C23、利用n个值作为叶结点的权生成的哈夫曼树中共包含有(

)个结点。A、nB、n+1C、2*nD、2*n-1正确答案：D24、二叉树的深度为k,则二叉树最多有（

）个结点。A、2kB、2k-1C、D、-1正确答案：D25、无向图的邻接矩阵是一个（

）。A、对称矩阵B、零矩阵C、上三角矩阵D、对角矩阵正确答案：A26、已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（

）。A、V1V2V4V8V3V5V6V7B、V1V2V4V5V8V3V6V7C、V1V2V4V8V5V3V6V7D、V1V3V6V7V2V4V5V8正确答案：C27、当两个元素出现逆序的时候就交换位置，这种排序方法称为（

）。A、插入排序B、交换排序C、选择排序D、归并排序正确答案：B28、在正常情况下，直接插入排序的时间复杂度为（

）。A、O(log2n)B、

O(n)C、

O(nlog2n)D、

O(n2)正确答案：D29、已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列从小到到大排序，经过一趟冒泡排序后的序列为（

）。A、16，28，34，54，73，62，60，26，43，95B、28，16，34，54，62，73，60，26，43，95C、28，16，34，54，62，60，73，26，43，95D、16，28，34，54，62，60，73，26，43，95正确答案：B二、填空题30、树的带权路径长度为树中所有叶子结点的

。正确答案：第1空:带权路径长度之和31、为了实现图的深度优先搜索遍历，其非递归的算法中需要使用的一个辅助数据结构为

。正确答案：第1空:栈32、在一个带权图中，两顶点之间的最段路径最多经过

条边。正确答案：第1空:n-133、结点的度是指结点所拥有的

。正确答案：第1空:子树数目或后继结点数34、中缀表达式(a+b)/c-(f-d/c)所对应的后缀表达式是

。正确答案：第1空:ab+c/fde/--35、树中度等于0的结点称作

或

。正确答案：第1空:叶子结点第2空:终端结点36、数据结构中的数据元素存在一对多的关系称为___结构。正确答案：第1空:树形结构;树结构37、数据结构中的数据元素存在一对一的关系称为_______

结构。正确答案：第1空:线性结构38、每个结点只包含一个指针域的线性表叫

。正确答案：第1空:单链表39、线性表具有

和

两种存储结构。正确答案：第1空:顺序存储第2空:链式存储;链接存储40、在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针

，当删除一个元素队列时，头指针

。正确答案：第1空:增1第2空:增141、栈是限定在表的一端进行插入和删除操作的线性表，又称为

。正确答案：第1空:后进先出表42、串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是

。正确答案：第1空:字符43、8．设广义表L=（（），（）），则L的长度是

。正确答案：第1空:244、若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是

。正确答案：第1空:6945、在有n个顶点的有向图中，每个顶点的度最大可达

。正确答案：第1空:2(n-1)三、简答题46、写出如下图所示的二叉树的先序、中序和后序遍历序列。正确答案：(1)先序为“根左右”，先序序列为：fdbacegihl

(2)中序为“左根右”，中序序列为：abcdefghij

(3)后序为“左右根”，后序序列为：acbedhjigf47、头指针、头结点、第一个结点（或称首元结点）的区别是什么？正确答案：头结点是在链表的开始结点之前附加的一个结点；第一个结点（或称首元结点）是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。48、简述栈和一般线性表的区别正确答案：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。49、简述广义表和线性表的区别和联系。正确答案：广义表是线性表的的推广，它也是n(n>0)个元素a1,a2…ai…an的有限序列，其中ai或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的特殊情况，当ai都是原子时，广义表退化成线性表。四、资料题50、已知序列（10，18，4，3，6，12，1，9，15，8），请写出对此序列采用归并排序法进行升序排序时各趟的结果。正确答案：第1空:答：原始序列：10，18，4，3，6，12，1，9，15，8第1趟：

[10，18][3，4][6，12][1，9][8，15]第2趟：

[3，4，10，18，][1，6，9，12][8，15]第3趟：

[3，4，10，18，][1，6，8，9，12，15]第4趟：

[1，3，4，6，8，9，10，12，15，18]51、intwrite(LinkQueue*q)

{QueueNode*p;

if(q->front==q->rear)

/*队空*/

{printf(“underflow”);

exit(0);}

while(q->front->next!=NULL)

{p=q->front->next;

(1)

printf(“%4d”,p->data);

(2)

}

（3）

;

/*队空时，头尾指针指向头结点*/

}正确答案：第1空:q->front->next=p->next;第2空:free(p);第3空:q->rear=q->front52、下列是在具有头结点单向列表中删除第i个结点，请在空格内填上适当的语句。intdelete(NODE*head,inti){NODE*p,*q;

intj;

q=head;j=0;

while((q!=NULL)&&(j找到要删除结点的直接前驱，并使q指向它*/

{q=q->next;j++;}

if(q==NULL)

return(0);（1）

;

（2）

;

free(p);

return(1);}正确答案：第1空:p=q->next第2空:q->next=p->next53、下列是用尾插法建立带头结点的且有n个结点的单向链表的算法，请在空格内填上适当的语句。NODE*create1(n)/*对线性表(1,2,.....,n),建立带头结点的单向链表*/{NODE*head,*p,*q;

inti;

p=(NODE*)malloc(sizeof(NODE));

head=p;q=p;p->next=NULL;

for(i=1;i<=n;i++)

{p=(NODE*)malloc(sizeof(NODE));

（1）

;

（2）

;

（3）

;

（4）

;

}

return(head);}正确答案：第1空:p->data=i第2空:p->next=NULL第3空:q->next=p第4空:q=p54、下列是用头插法建立带头结点的且有n个结点的单向链表的算法，请在空格内填上适当的语句。NODE*create2(n)/*对线性表(n,n-1,.....,1),建立带头结点的线性链表*/{NODE*head,*p,*q;

inti;

p=(NODE*)malloc(sizeof(NODE));

（1）

;

p->next=NULL;

（2）

;

for(i=1;i<=n;i++)

{p=(NODE*)malloc(sizeof(NODE));

p->data=i;

if(i==1)

（3）

;

else（4）

;（5）

;}

return(head);}正确答案：第1空:head=p第2空:q=p第3空:p->next=NULL第4空:p->next=q->next第5空:q->next=p55、已知无向图G描述如下：G=（V，E）V={V1，V2，V3，V4，V5}E={（V1，V2），（V1，V4），（V2，V4），（V3，V4），（V2，V5），（V3，V4），（V3，V5）}（1）画出G的图示；（2）然后给出G的邻接矩阵和邻接表；（3）写出每个顶点的度。正确答案：第1空:G的图示第2空:第3空:V1、V2、V3、V4、V5的度分别为：2，3，2，3，22023学年6月份考试数据结构复习题一、单选题1、算法分析的目的是（）。A、找出数据结构的合理性B、研究算法中的输入和输出的关系C、分析算法的效率以求改进分析算法的易懂性和文档性D、分析算法的易懂性和文档性正确答案：C2、算法的时间复杂度与（）有关。A、所使用的计算机B、计算机的操作系统C、算法本身D、数据结构正确答案：C3、下列的叙述中，不属于算法特性的是（）。A、有穷性B、输入性C、可行性D、可读性正确答案：D4、在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（）。A、f->next=s;f=s;B、r->next=s;r=s;C、s->next=r;r=s;D、s->next=f;f=s;正确答案：B5、串是（）。A、不少于一个字母的序列B、任意个字母的序列C、不少于一个字符的序列D、有限个字符的序列正确答案：D6、每次把待排序的区间划分为左、右两个子区间，其中左区间中记录的关键字均小于等于基准记录的关键字，右区间中记录的关键字均大于等于基准记录的关键字，这种排序称为（）。A、插入排序B、快速排序C、堆排序D、归并排序正确答案：B7、下列说法中，不正确的是（）。A、数据元素是数据的基本单位B、数据项是数据中不可分割的最小可标识单位C、数据可有若干个数据元素构成D、数据项可由若干个数据元素构成正确答案：D8、从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称为（）A、插入排序B、选择排序C、交换排序D、归并排序正确答案：A9、在一个有像图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A、邻接矩阵表示法B、邻接表表示法C、逆邻接表表示法D、邻接表和逆邻接表正确答案：B10、在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（）。A、f->next=s;f=s;B、r->next=s;r=s;C、s->next=r;r=s;D、s->next=f;f=s;正确答案：B11、常对数组进行的两种基本操作是（）。A、建立与删除B、索引和修改C、查找和修改D、查找与索引正确答案：C12、假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）。A、15B、16C、17D、47正确答案：B13、设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（）。A、n-i+1B、n-iC、n-i-1D、i正确答案：A14、将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（）。A、33B、34C、35D、36正确答案：B15、无向图的邻接矩阵是一个（）。A、对称矩阵B、零矩阵C、上三角矩阵D、对角矩阵正确答案：A16、用某种排序的方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：（1）25，84，21，47，15，27，68，35，20（2）20，15，21，25，47，27，68，35，84（3）15，20，21，25，35，27，47，68，84（4）15，20，21，25，27，35，47，68，84其所采用的排序方法是（）。A、希尔排序B、归并排序C、快速排序D、直接选择排序正确答案：C17、在一棵树中，（）没有前驱结点。A、分支结点B、叶结点C、树根结点D、空结点正确答案：C18、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。A、完全图B、连通图C、有回路D、一棵树正确答案：B19、一组记录的关键字序列为（46，79，56，38，40，84），利用堆排序的方法建立的初始堆为（）。A、79，46，56，38，40，84B、84，79，56，38，40，46C、84，79，56，46，40，38D、84，56，79，40，46，38正确答案：B20、判断栈S满（元素个数最多n个）的条件是（）。A、s->top==0B、s->top!=0C、s-->top==n-1D、s->top!=n-1正确答案：C二、填空题21、哈夫曼树又称_______________最优二叉树22、中缀表达式(a+b)/c-(f-d/c)所对应的后缀表达式是。ab+c/fde/--23、树的度是指。树24、折半查找只适用于的有序表顺序存储结构25、从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行x=h->data;和________。(结点的指针域为next)h=h->next26、将树中结点赋上一个有着某种意义的实数，称此实数为该结点的。权27、在一个查找表中，能够唯一地确定一个记录的关键字称为。主关键字28、具有m个叶子结点的哈夫曼树共有结点。2m-129、串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是。字符30、根据排序过程中所用的存储器不同，可以将排序方法分为__________和。内部排序外部排序31、数据结构按结点间的关系，可分为4种逻辑结构：、、、。集合结构线性结构树形结构；树结构图状结构；三、简答题32、简述广义表和线性表的区别和联系。广义表是线性表的的推广，它也是n(n>0)个元素a1,a2…ai…an的有限序列，其中ai或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的特殊情况，当ai都是原子时，广义表退化成线性表。33、头指针、头结点、第一个结点（或称首元结点）的区别是什么？头结点是在链表的开始结点之前附加的一个结点；第一个结点（或称首元结点）是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。四、资料题34、下列是在具有头结点单向列表中删除第i个结点，请在空格内填上适当的语句。intdelete(NODE*head,inti){NODE*p,*q;intj;q=head;j=0;while((q!=NULL)&&(j找到要删除结点的直接前驱，并使q指向它*/{q=q->next;j++;}if(q==NULL)return(0);（1）;（2）;free(p);return(1);}p=q->nextq->next=p->next数据结构期末考试复习题注：找到所考试题直接看该试题所有题目和答案即可。查找按键：Ctrl+F超越高度一、单选题1、当两个元素出现逆序的时候就交换位置，这种排序方法称为（

）。A、插入排序B、交换排序

C、选择排序D、归并排序正确答案：B2、有关线性表的正确说法是（

）。A、每个元素都有一个直接前驱和一个直接后继

B、线性表至少要求一个元素C、表中的元素必须按由小到大或由大到下排序D、除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继正确答案：D3、在下列排序方法中，关键字比较的次数与记录的初始排列秩序无关的是（

）。A、希尔排序B、冒泡排序C、插入排序D、选择排序正确答案：D4、串是（

）。A、不少于一个字母的序列B、任意个字母的序列C、不少于一个字符的序列D、有限个字符的序列

正确答案：D5、向顺序栈中压入新元素时，应当（

）。A、先移动栈顶指针，再存入元素B、先存入元素，再移动栈顶指针C、先后次序无关紧要

D、同时进行正确答案：A6、有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（

）。A、29/10B、31/10C、26/10D、29/9正确答案：A7、已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较（

）次。A、3B、4C、5D、6正确答案：C8、从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称为（

）A、插入排序

B、选择排序C、交换排序D、归并排序正确答案：A9、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（

）。A、nB、eC、2nD、2e正确答案：D10、在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（

）。A、top->next=p;

B、p->next=top->next;top->next=p;C、p->next=top;top=p;

D、p->next=top->next;top=top->next;正确答案：C11、在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（

）。A、f->next=s;f=s;

B、r->next=s;r=s;

C、s->next=r;r=s;

D、s->next=f;f=s;正确答案：B12、一个队列的入队序列是1，2，3，4。则队列的输出序列是（

）。A、4，3，2，1

B、1，2，3，4

C、1，4，3，2

D、3，2，4，1正确答案：B13、带头结点的链表为空的判断条件是（

）（设头指针为head）。A、head

=

=NULLB、head->next=

=NULL

C、head->next=

=head

D、head!=NULL正确答案：B14、在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（

）。A、p->next=s;sànext=pànext

B、p->next=sànext;C、p=s->next；

D、s->next=p->next;p->next=s;正确答案：D15、一个队列的入队顺序是a,b,c,d，则离队的顺序是（

）。A、a,d,c,b

B、a,b,c,d

C、d,c,b,aD、c,b,d,a正确答案：B16.数据结构中，与所使用的计算机无关的是数据的（

）。A.存储结构B.物理结构C.逻辑结构D.物理和存储结构正确答案：C17.已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较（

）次。A.3B.4C.5D.6正确答案：C18.图的深度优先遍历算法类似于二叉树的（

）遍历。A.先序B.中序C.后序D.层次正确答案：A19.常对数组进行的两种基本操作是（

）。A.建立与删除B.索引和修改C.查找和修改D.查找与索引正确答案：C20.若串S==“English”，其子串的个数是（

）。A.9B.16

C.36D.28正确答案：D二、填空题1、哈夫曼树又称为

正确答案：第1空:最优二叉树2、结点的度是指结点所拥有的

。正确答案：第1空:子树数目或后继结点数3、图常用的两种存储结构是

和

。正确答案：第1空:邻接矩阵第2空:邻接表4、将树中结点赋上一个有着某种意义的实数，称此实数为该结点的

。正确答案：第1空:权5、在一个带权图中，两顶点之间的最段路径最多经过

条边。正确答案：第1空:n-16、关键字是记录某个

，用它可以识别、确定一个记录。正确答案：第1空:数据项的值7、广义表A（（a,b,c）,(d,e,f)）的表尾为

。正确答案：第1空:（（d,e,f））8、循环队列队头指针在队尾指针

位置，队列是“满”状态正确答案：第1空:下一个9、

查找是一种最简单的查找方法。正确答案：第1空:顺序10、为了实现图的深度优先搜索遍历，其非递归的算法中需要使用的一个辅助数据结构为

。正确答案：第1空:栈11、树中度大于0的结点称作

或

。答案：(1)分支结点(2)非终端结点12、在队列的顺序存储结构中，当插入一个新的队列元素时，尾指

，当删除一个元素队列时，头指针

。答案：(1)增1(2)增113、具有m个叶子结点的哈夫曼树共有

结点。答案：(1)2m-114、冒泡排序是一种比较简单的

方法。答案：(1)交换排序15、在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种

的关系答案：(1)多对多三、简答题1、简述栈和一般线性表的区别正确答案：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。2、写出以下运算式的后缀算术运算式:(A+B)*C-D/(E+F)+G正确答案：AB+C*DEF+/-G+3、编写顺序查找算法。顺序查找算法如下：

intsearch(NODEa[],intn,intk)

/*在a[0]～a[n-1]中顺序查找关键字等于k的记录。查找成功时返回该记录的下标，失败时返回-1*/

{

}intsearch(NODEa[],intn,intk)

/*在a[0]～a[n-1]中顺序查找关键字等于k的记录。查找成功时返回该记录的下标，失败时返回-1*/

{

inti=0;

while(i<n&&a[i].key!=k)/*没有查到同时查找过程没有结束，则继续查找*/

i++;

if(a[i].key=k)

/*查找成功*/

returni;

elsereturn-1;

/*查找失败*/}4、简述广义表和线性表的区别和联系。答案：广义表是线性表的的推广，它也是n(n>0)个元素a1

,a2…ai…

an的有限序列，其中ai或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的特殊情况，当ai都是原子时，广义表退化成线性表。四、资料题1、已知无向图G描述如下：G=（V，E）V={V1，V2，V3，V4，V5}E={（V1，V2），（V1，V4），（V2，V4），（V3，V4），（V2，V5），（V3，V4），（V3，V5）}（1）画出G的图示；（2）然后给出G的邻接矩阵和邻接表；（3）写出每个顶点的度。正确答案：第1空:G的图示
第2空:
第3空:V1、V2、V3、V4、V5的度分别为：2，3，2，3，22、下面函数的功能是返回二叉树BT中值为X的结点所在的层号，请在划有横线的地方填写合适内容。

intNodeLevel(structBinTreeNode*BT,charX)

{

if(BT==NULL)return0;

/*空树的层号为0*/

elseif(BT->data==X)return1;

/*根结点的层号为1*/

/*向子树中查找X结点*/

else{

intc1=NodeLevel(BT->left,X);

if(c1>=1)___(1)___________;

intc2=______(2)__________;

if___(3)__________________;

//若树中不存在X结点则返回0

elsereturn0;

}

}正确答案：第1空:

returnc1+1第2空:

NodeLevel(BT->right,X)第3空:

(c2>=1)returnc2+12022学年9月份考试数据结构复习题一、单选题1、数据结构中，与所使用的计算机无关的是数据的（

）。A、存储结构B、物理结构C、逻辑结构D、物理和存储结构正确答案：C2、在下列排序方法中，关键字比较的次数与记录的初始排列秩序无关的是（

）。A、希尔排序B、冒泡排序C、插入排序D、选择排序正确答案：D3、在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（

）。A、p=q->nextB、p->next=q

C、p->next=q->nextD、q->next=NULL正确答案：C4、已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较（

）次。A、3B、4C、5D、6正确答案：C5、从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称为（

）A、插入排序

B、选择排序C、交换排序D、归并排序正确答案：A6、图的深度优先遍历算法类似于二叉树的（

）遍历。A、先序B、中序C、后序D、层次正确答案：A7、二叉树第k层上最多有（

）个结点。

A、2kB、C、-1D、2正确答案：B8、常对数组进行的两种基本操作是（

）。A、建立与删除B、索引和修改C、查找和修改D、查找与索引正确答案：C9、若串S==“English”，其子串的个数是（

）。A、9B、16

C、36D、28正确答案：D10、一个队列的入队顺序是a,b,c,d，则离队的顺序是（

）。A、a,d,c,b

B、a,b,c,d

C、d,c,b,aD、c,b,d,a正确答案：B11、设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（

）。A、n-i+1B、n-iC、n-i-1D、i正确答案：B12、顺序查找方法适合于存储结构为（

）的线性表。A、散列存储B、索引存储C、散列存储或索引存储D、顺序存储或链接存储正确答案：D13、利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为(

)。A、18B、16C、12D、30正确答案：A14、设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（

）。A、abdecB、debacC、debcaD、abedc正确答案：C15、下列有关二叉树的说法正确的是（

）。A、二叉树中度为0的结点的个数等于度为2的结点的个数加1B、二叉树中结点个数必大于0C、完全二叉树中，任何一个结点的度，或者为0或者为2

D、二叉树的度是2正确答案：A16、算法的时间复杂度与（）有关。A、所使用的计算机B、计算机的操作系统C、算法本身D、数据结构正确答案：C17、算法分析的目的是（）。A、找出数据结构的合理性B、研究算法中的输入和输出的关系C、分析算法的效率以求改进分析算法的易懂性和文档性D、分析算法的易懂性和文档性正确答案：C18、链表不具有的特点是（）。A、可随机访问任一元素B、插入删除不需要移动元素C、不必事先估计存储空间D、所需空间与线性表长度成正比正确答案：A19、在图的存储结构表示中，表示形式唯一的是（）。A、nB、n+1C、n-1D、n/2正确答案：C20、对于顺序存储的有序表{5，12，20，26，37，42，46，50，64}，若采用折半查找，则查找元素26的比较次数是（）。A、2B、3C、4D、5正确答案：C21、以下陈述中正确的是（

）。A、串是一种特殊的线性表B、串的长度必须大于零C、串中元素只能是字母

D、空串就是空白串正确答案：A22、设有两个串p和q，其中q是p的子串，q在p中首次出现的位置的算法称为（

）。A、求子串B、连接C、匹配D、求串长正确答案：C23、串是（

）。

A、不少于一个字母的序列B、任意个字母的序列C、不少于一个字符的序列D、有限个字符的序列

正确答案：D解析：24、串的长度是指（

）。A、串中所含不同字母的个数B、串中所含字符的个数C、串中所含不同字符的个数D、串中所含非空格字符的个数正确答案：B25、两个字符串相等的条件是（

）。A、两串的长度相等B、两串包含的字符相同C、两串的长度相等，并且两串包含的字符相同D、两串的长度相等，并且对应位置上的字符相同正确答案：D二、填空题1、树中度大于0的结点称作

或

。正确答案：第1空:分支结点第2空:非终端结点2、哈夫曼树又称为

正确答案：第1空:最优二叉树3、在一棵树中，每个结点的子树的根或者说每个结点的

称为该结点的孩子结点，简称为孩子。正确答案：第1空:后继结点4、树中度等于0的结点称作

或

。正确答案：第1空:叶子结点第2空:终端结点5、图常用的两种存储结构是

和

。正确答案：第1空:邻接矩阵第2空:邻接表6、在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针

，当删除一个元素队列时，头指针

。正确答案：第1空:增1第2空:增17、在对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需要比较

次。正确答案：第1空:38、关键字是记录某个

，用它可以识别、确定一个记录。正确答案：第1空:数据项的值9、具有m个叶子结点的哈夫曼树共有

结点。正确答案：第1空:2m-110、串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是

。正确答案：第1空:字符11、在一个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点。则可以用操作___。正确答案：第1空:q->next=p->next

12、冒泡排序是一种比较简单的

方法。正确答案：第1空:交换排序13、单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针改为

；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向

。正确答案：第1空:头结点的指针第2空:指向第一个结点的指针14、在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种

的关系正确答案：第1空:多对多15、数据结构中的数据元素存在多对多的关系称为____结构。正确答案：第1空:图状结构;图结构16、分块查找又称为

，它是一种介于顺序查找和折半查找之间的查找方法。正确答案：第一空：

索引顺序查找17、在有序表A[1….18]中，采用二分查找算法查找元素值等于A[17]的元素，所比较过的元素的下标依次是

。正确答案：第一空：

9，

14，

16

，1718、栈是限定在表的一端进行插入和删除操作的线性表，又称为

。正确答案：第一空：

后进先出表19、在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针

，当删除一个元素队列时，头指针

。正确答案：第一空：

增1第二空：

增120、广义表A（（a,b,c）,(d,e,f)）的表尾为

。正确答案：第一空：

（（d,e,f））三、简答题1、编写顺序查找算法。顺序查找算法如下：

intsearch(NODEa[],intn,intk)

/*在a[0]～a[n-1]中顺序查找关键字等于k的记录。查找成功时返回该记录的下标，失败时返回-1*/

{

}正确答案：顺序查找算法如下：

intsearch(NODEa[],intn,intk)

/*在a[0]～a[n-1]中顺序查找关键字等于k的记录。查找成功时返回该记录的下标，失败时返回-1*/

{

inti=0;

while(i<n&&a[i].key!=k)/*没有查到同时查找过程没有结束，则继续查找*/

i++;

if(a[i].key=k)

/*查找成功*/

returni;

elsereturn-1;

/*查找失败*/}2、简述栈和一般线性表的区别正确答案：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。3、简述队列和一般线性表的区别。正确答案：队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。4、(1)

设有查找表{8,17,5,9,21,10,7,19,6},依次取表中数据，构造一棵二叉排序树.（2）说明如何通过序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果.正确答案：1.2.中序遍历：2，3，4，5，6，7，14，16，18四、资料题1、下面函数的功能是返回二叉树BT中值为X的结点所在的层号，请在划有横线的地方填写合适内容。

intNodeLevel(structBinTreeNode*BT,charX)

{

if(BT==NULL)return0;

/*空树的层号为0*/

elseif(BT->data==X)return1;

/*根结点的层号为1*/

/*向子树中查找X结点*/

else{

intc1=NodeLevel(BT->left,X);

if(c1>=1)___(1)___________;

intc2=______(2)__________;

if___(3)__________________;

//若树中不存在X结点则返回0

elsereturn0;

}

}正确答案：第一空：

returnc1+1第二空：

NodeLevel(BT->right,X)第三空：

(c2>=1)returnc2+12、阅读下面算法，在划线处填入正确的代码内容intwrite(LinkQueue*q)

{QueueNode*p;

if(q->front==q->rear)

/*队空*/

{printf(“underflow”);

exit(0);}

while(q->front->next!=NULL)

{p=q->front->next;

(1)

printf(“%4d”,p->data);

(2)

}

（3）

;

/*队空时，头尾指针指向头结点*/

}正确答案：第一空：

q->front->next=p->next;第二空：

free(p);第三空：

q->rear=q->front一、

单选题

1、一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的存储地址为100，则该数组的首地址是（

）。A、

64B、

28C、

70D、

90答案：

C

2、下述几种排序方法中，平均情况下占用内存量最大的是（

）方法。A、插入排序B、选择排序C、快速排序D、归并排序答案：

D3、在数据结构中，从逻辑上可以把数据结构分为（

）。A、

动态结构和静态结构

B、

紧凑结构和非紧凑结构

C、

线性结构和非线性结构

D、

内部结构和外部机构

答案：

C

4、在一个有像图中，所有顶点的入度之和等于所有顶点的出度之和的（

）倍。A、

邻接矩阵表示法

B、

邻接表表示法

C、

逆邻接表表示法D、

邻接表和逆邻接表答案：

B

5、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（

）。A、

nB、

n/2

C、(n+1)/2

D、(n-1)/2

答案：

C

6、一个存储结点存储一个（

）。A、

数据项

B、

数据元素

C、

数据结构

D、

数据类型

答案：

B

7、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（

）。A、nB、eC、2nD、2e答案：

D

8、

一个顺序表第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的地址是（

）。

A、

98

B、

100

C、

102

D、

106

答案：

B

9、常对数组进行的两种基本操作是（

）。A、

建立与删除B、

索引和修改C、

查找和修改D、

查找与索引答案：

C

10、在实际应用中，要输入多个字符串，且长度无法预定。则应该采用（

）存储比较合适。A、链式

B、顺序C、堆结构

D、无法确定

答案：

A

11、在下列排序方法中，关键字比较的次数与记录的初始排列秩序无关的是（

）。

A、希尔排序B、冒泡排序C、插入排序D、选择排序答案：

D

12、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（

）结构。A、

堆栈B、

队列C、

数组D、

线性表答案：

B

13、向顺序栈中压入新元素时，应当（

）。A、

先移动栈顶指针，再存入元素

B、

先存入元素，再移动栈顶指针

C、

先后次序无关紧要

D、

同时进行

答案：

A

14、哈希函数有一个共同的性