数据结构试卷A及答案

《数据结构》试卷A     

一、填空，请将答案写在横线上（每空2分，共20分）

1.数据的逻辑结构是从逻辑关系上描述数据，它与数据的_____无关，是于计算机的。

2.在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=                。

3.栈顶的位置是随着                操作而变化的。

4.在有序表（12，24，36，48，60，72，84）中二分查找关键字48时所需进行的关键字比较次数为    。

5.多重表文件和倒排文件都归属于                文件。

6.链表适用于                查找。

7.队列的插入操作在            进行，删除操作在             进行。

8.数据的基本存储方式为顺序存储方式、链式存储方式和            、            四种。

二、是非题（用“√”、“×”分别标记正确与错误的说法。每小题1分，共10分）：

1.线性表的逻辑顺序与物理顺序总是一致的。（  ）

2.线性表的顺序存储表示优于链式存储表示。（  ）

3.线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（  ）

4.二维数组是其数组元素为线性表的线性表。（  ）

5.每种数据结构都应具备三种基本运算：插入、删除和搜索。（  ）

6.二维数组可以视为数组元素为一维数组的一维数组。（  ）

7.链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，通常存储器中还有空闲存储空间，就不会产生存储溢出的问题。（   ）

8.在用单链表表示的链式队列中，队头在链表的链尾位置。（   ）

9.凡是递归定义的数据结构都可以用递归算法来实现它的操作。（   ）

10.进行折半搜索的表必须是顺序存储的有序表。（   ）

三、单项选择题，在括号内填写所选择的标号。（每小题2分，共计30分）

1．算法指的是（   ）

       A．计算机程序             B．解决问题的计算方法

C．排序算法               D．解决问题的有限运算序列

2．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（  ）

 A．O（1）         B．O（n）        C．O（m）       D．O（m+n）

3．由两个栈共享一个向量空间的好处是：（   ）

   A．减少存取时间，降低下溢发生的机率

   B．节省存储空间，降低上溢发生的机率

   C．减少存取时间，降低上溢发生的机率

   D．节省存储空间，降低下溢发生的机率

4．如下陈述中正确的是（    ）

   A．串是一种特殊的线性表           B．串的长度必须大于零

   C．串中元素只能是字母             D．空串就是空白串

5．一个非空广义表的表头（    ）

   A．不可能是子表                B．只能是子表

   C．只能是原子                  D．可以是子表或原子

6．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为(    )

    A．4           B．5            C．6          D．7

7．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为(    )

    A．e           B．2e           C．n2－e         D．n2－2e

8．假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是(    )

A．O(n)        B．O(e)         C．O(n+e)        D．O(n*e)

9．适于对动态查找表进行高效率查找的组织结构是（   ）

    A．有序表       B．分块有序表       C．三叉排序树       D．线性链表

10．不定长文件是指（   ）

    A．文件的长度不固定            B．记录的长度不固定

C．字段的长度不固定            D．关键字项的长度不固定

11．假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为(   )

     A. front == rear                B. front != NULL

     C. rear != NULL                D. front == NULL

12. 图的广度优先搜索类似于树的（      ）次序遍历。 

     A. 先根           B. 中根           C. 后根           D. 层次

13．若让元素1，2，3依次进栈，则出栈次序不可能出现（    ）种情况。

A．3，2，1       B．2，1，3         C．3，1，2           D．1，3，2

14．一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（  ）

A．较快          B．较慢            C．相同 

15.树中所有结点的度等于所有结点数加（  ）

A．0             B．1               C．-1                D．2

四、算法阅读题.（每小题20分，共计40分）

1.下列算法的功能是比较两个链串的大小， 

请在空白处填入适当的内容。

int comstr(LinkString s1,LinkString s2) 

{//s1和s2为两个链串的头指针

   while(s1&&s2){

      if(s1－>datedate)return－1；

      if(s1－>date>s2－>date)return1；

          ①    ；

          ②    ；

       }     

       if(  ③   )return－1；

       if(  ④   )return1；

⑤   ；

     }

①                     

②                     

③                     

④                     

⑤                     

2. 阅读下面的算法

       LinkList mynote(LinkList L)

       {//L是不带头结点的单链表的头指针

             if(L&&L->next){

                  q=L；L=L－>next；p=L；

        S1：       while(p－>next) p=p－>next；

        S2：       p－>next=q；q－>next=NULL；

              } 

              return  L；

            }

    请回答下列问题：

   （1）说明语句S1的功能；

   （2）说明语句组S2的功能； 

（3）设链表表示的线性表为（a1,a2, …,an）,写出算法执行后的返回值所表示的线性表。

《数据结构》试卷A答案

一、填空，请将答案写在答题卡上（每空1.5分，共15分）：

1.存储（或存储结构）        2. p－>next－>next        3. 进栈和退栈        4.1

5. 多关键字        6. 顺序        7. 队尾  队头        8.索引存储方式、散列存储方式

二、是非题（每小题1分，共10分）：

1、2、4、8错                                    3、5、6、7、9、10对

三、单项选择题，在括号内填写所选择的标号。（每小题1分，共计20分）

1－5：DCBAD        6－10：CDCCB            11－15：DDCBC

四、算法阅读题

1.     ①S1=S1－>next

    ②s2=s2－>next

    ③s2(或s2!=NULL或s2&&!s1)

       ④s1(或s1!=NULL或s1&&!s2)

⑤return 0

2. （1）查询链表的尾结点

   （2）将第一个结点链接到链表的尾部，作为新的尾结点

   （3）返回的线性表为（a2,a3,…,an,a1）