全国自考（数据结构）模拟试卷4

如果您发现本试卷没有包含本套题的全部小题，请尝试在页面顶部本站内搜索框搜索相关题目，一般都能找到。

34．采用单链表作为存储结构，试编写一个函数来实现用选择排序方法进行升序排列。
点击查看答案
33．基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的列序来进行转置，请在______处用适当的语句予以填充。
Trans_Sparmat(SpMatrixTp a,SpMatrixTp*b)
  {(*b).mum=a.nu;(*b).nu=a.mu;(*b).tu=a.tu
    if(a.tu)
      { q=1;
         for(col=1;______;col++)
         for(p=1;p＜=a.tu;p++)
          if(______)==col)
           { (*b).data[q].i=a.data[p].j;
             (*b).data[q].j=a.data[p].i;
             (*b).data[q].v=a.data[p].v;
             ______;
           }
      }
  }
点击查看答案
32．以下算法在开散列表HP中查找键值等于K的结点，成功时返回指向该点的指针，不成功时返回空指针。请分析程序，并在______上填充合适的语句。
pointer research_openhash(keytypeK,openhash HP)
  {i=H(K);   /*计算K的散列地址*/
    p=HP[i];   /*i的同义词子表表头指针传给P*/
    while(______)p=p—＞next; /*未达到表尾且未找到时，继续扫描*/
    ______;
  }
点击查看答案
30． INITIATE()的功能是建立一个空表。请在______处填上正确的语句。
lklist initiate_lklist() /*建立一空表*/
{______;
______;
return(t);
}
点击查看答案
31．以下运算实现在顺序栈上的退栈，请在______处用适当的语句予以填充。
int Pop(SqStackTp*sq,DataType*x)
     { if(sq—＞top==0){error("下溢");return(0);)
        else{*x=______;
                ______;
                return(1);
     }
  }
点击查看答案
27．对于如下一个有序的关键字序列{5,9,12,18,23,31,37,46,59,66,71,78,85)，现在要求用二分法进行查找值为18的关键字，则经过几次比较之后能查找成功?
点击查看答案
29．已知数据序列为{12,5,9,20,6,31,24)，对该数据序列进行排序，试写出插入排序和冒泡排序每趟的结果。
点击查看答案
28．已知有一关键字序列为{505,94,512,61,908,170,897,275,653,463)，如果我们采用快速法对此序列进行排序(按照升序排序)，请给出每一趟排序的结果。
点击查看答案
26．请根据下面所给出的邻接矩阵画出相应的有向图或者是无向图(顶点v_i表示)。
点击查看答案
25．查找表按其所包括的运算的不同分为______查找表和______查找表。
点击查看答案
24．在具有n个单元的循环队列中，队满时共有______个元素。
点击查看答案
23．在线性表的顺序存储中，假设每个结点所占用的存储空间为c，且第一个单元的存储地址则是该结点的存储地址，设开始结点a₁的存储地址是LOC(a₁)，则结点a₁存储地址LOC(a₁)可以通过下式得到______。
点击查看答案
20．数组0[1……n]表示一个环形队列，设f的值为队列中第一个元素的位置，r的值为队列中实际队尾元素的位置加1，并假定队列中至多只有n-1个元素，则计算队列中元素个数的公式为______。
点击查看答案
22．一个n×n的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为______。
点击查看答案
21．一般来说，数组中的元素具有______的数据类型，并且数组元素的下标的上界和下界都是______的。
点击查看答案
19．在二叉排序树中，其左子树中任何一个结点的关键字一定______其右子树的各结点的关键字。
点击查看答案
18．对于一个长度为n的线性表，假设表中各结点的查找概率相同，则在查找成功的情况下，平均查找长度为______，如果k不在表中，则需要进行______次比较后才能确定查找失败。
点击查看答案
17．设有两个串p和q，求q在p中首次出现的位置的运算叫______。
点击查看答案
16．对于一个具有n个结点的单链表，在已知p结点后插入一个新结点的事件的时间复杂性为______，在给定值为x的结点后插入一个新结点的时间复杂性为______。
点击查看答案
14．设图G采用邻接表存储，则拓扑排序算法的时间复杂度为( )
- A．O(n)
- B．O(n+e)
- C．O(n²)
- D．O(n×e)
点击查看答案
15．在下面的排序方法中，属于不稳定的排序方法的是( )
- A．直接插入排序
- B．冒泡法排序
- C．堆排序
- D．归并排序
点击查看答案
13．在一非空二叉树的中序遍历序列中，根结点的右边( )
- A．只有右子树上的所有结点
- B．只有右子树上的部分结点
- C．只有左子树上的所有结点
- D．只有左子树上的部分结点
点击查看答案
11．线索二叉树是一种( )结构。
- A．物理
- B．逻辑
- C．存储
- D．线性
点击查看答案
12．排序的重要目的是为了以后对已排序的数据元素进行( )
- A．打印输出
- B．分类
- C．查找
- D．合并
点击查看答案
10．邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的( )
- A．先序遍历
- B．中序遍历
- C．后序遍历
- D．按层遍历
点击查看答案
9．设散列函数为H(k)=k mod7，一组关键码为23,14,9,6,30,12和18，散列表T的地址空间为0.6，用线性探测法解决冲突，依次将这组关键码插入T中，得到的散列表为( )
- A.A
- B.B
- C.C
- D.D
点击查看答案
7．从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较( )个结点。
- A．n
- B．n/2
- C．(n-1)/2
- D．(n+1)/2
点击查看答案
8．在一个链队列中，若f，r分别为队首、队尾指针，则插入s所指结点的操作为( )
- A．f—＞next=c;f=s;
- B．r—＞next=s;r=s;
- C．s—＞next=r;r= s
- D．s—＞next=f,f=s;
点击查看答案
4．非空的单循环链表L的尾结点P↑，满足( )
- A．P↑.next=NULL;
- B．P=NULL;
- C．P↑.next=L;
- D．P=L
点击查看答案
5．在下面的排序方法中，不需要通过比较关键字就能进行排序的是( )
- A．箱排序
- B．快速排序
- C．插入排序
- D．希尔排序
点击查看答案
6．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着( )
- A．数据元素具有同一特点
- B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
- C．每个数据元素都一样
- D．数据元素所包含的数据项的个数要相等
点击查看答案
3．带头结点的单链表head为空的判断条件是( )
- A．head=NULL
- B．head—＞next=NULL
- C．head—＞next=head
- D．head!=NULL
点击查看答案
2．一个栈的人栈序列是a,b,c,d,e，则栈的不可能的输出序列是( )
- A．e d c b a
- B．d e c b a
- C．d c e a b
- D．a b c d e
点击查看答案
1．对文件进行直接存取的是根据( )
- A．逻辑记录号去存取某个记录
- B．逻辑记录的关键字去存取某个记录
- C．逻辑记录的结构去存取某个记录
- D．逻辑记录的具体内容去存取某个记录
点击查看答案

全国自考（数据结构）模拟试卷4

34．采用单链表作为存储结构，试编写一个函数来实现用选择排序方法进行升序排列。

30． INITIATE()的功能是建立一个空表。请在______处填上正确的语句。
lklist initiate_lklist() /建立一空表/
{;
;
return(t);
}

31．以下运算实现在顺序栈上的退栈，请在处用适当的语句予以填充。
int Pop(SqStackTpsq,DataTypex)
     { if(sq—＞top==0){error("下溢");return(0);)
        else{*x=;
                __;
                return(1);
     }
  }

27．对于如下一个有序的关键字序列{5,9,12,18,23,31,37,46,59,66,71,78,85)，现在要求用二分法进行查找值为18的关键字，则经过几次比较之后能查找成功?

29．已知数据序列为{12,5,9,20,6,31,24)，对该数据序列进行排序，试写出插入排序和冒泡排序每趟的结果。

28．已知有一关键字序列为{505,94,512,61,908,170,897,275,653,463)，如果我们采用快速法对此序列进行排序(按照升序排序)，请给出每一趟排序的结果。

26．请根据下面所给出的邻接矩阵画出相应的有向图或者是无向图(顶点v_i表示)。

25．查找表按其所包括的运算的不同分为查找表和查找表。

24．在具有n个单元的循环队列中，队满时共有______个元素。

23．在线性表的顺序存储中，假设每个结点所占用的存储空间为c，且第一个单元的存储地址则是该结点的存储地址，设开始结点a₁的存储地址是LOC(a₁)，则结点a₁存储地址LOC(a₁)可以通过下式得到______。

20．数组0[1……n]表示一个环形队列，设f的值为队列中第一个元素的位置，r的值为队列中实际队尾元素的位置加1，并假定队列中至多只有n-1个元素，则计算队列中元素个数的公式为______。

22．一个n×n的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为______。

21．一般来说，数组中的元素具有的数据类型，并且数组元素的下标的上界和下界都是的。

19．在二叉排序树中，其左子树中任何一个结点的关键字一定______其右子树的各结点的关键字。

18．对于一个长度为n的线性表，假设表中各结点的查找概率相同，则在查找成功的情况下，平均查找长度为，如果k不在表中，则需要进行次比较后才能确定查找失败。

17．设有两个串p和q，求q在p中首次出现的位置的运算叫______。

16．对于一个具有n个结点的单链表，在已知p结点后插入一个新结点的事件的时间复杂性为，在给定值为x的结点后插入一个新结点的时间复杂性为。

14．设图G采用邻接表存储，则拓扑排序算法的时间复杂度为( )

15．在下面的排序方法中，属于不稳定的排序方法的是( )

13．在一非空二叉树的中序遍历序列中，根结点的右边( )

11．线索二叉树是一种( )结构。

12．排序的重要目的是为了以后对已排序的数据元素进行( )

10．邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的( )

9．设散列函数为H(k)=k mod7，一组关键码为23,14,9,6,30,12和18，散列表T的地址空间为0.6，用线性探测法解决冲突，依次将这组关键码插入T中，得到的散列表为( )

7．从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较( )个结点。

8．在一个链队列中，若f，r分别为队首、队尾指针，则插入s所指结点的操作为( )

4．非空的单循环链表L的尾结点P↑，满足( )

5．在下面的排序方法中，不需要通过比较关键字就能进行排序的是( )

6．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着( )

3．带头结点的单链表head为空的判断条件是( )

2．一个栈的人栈序列是a,b,c,d,e，则栈的不可能的输出序列是( )

1．对文件进行直接存取的是根据( )