数据结构（C#语言）

线下作业

学生姓名:                   

学生学号:                   

作业总成绩:                   

线下作业说明

成绩计算说明：

“线下作业”为课程考核方案中“线下学习”一个考核项，其占“线下学习”的28%。本课程共4次“线下作业”，按百分制计。因此，“线下作业总成绩”计算方法如下：

线下作业总成绩=【线下作业1得分（百分制） *25%+线下作业2得分（百分制） *25%+线下作业3得分（百分制） *25%+线下作业4得分（百分制） *25%】*28%

作业提交说明：

    同学在作答完成后，需要线下提交给辅导教师进行评阅打分。

单选题，每题10分，共100分

1、【单选题】一个记录的关键字为（46，79，56，38，40，84），采用快速排序以第一个记录为基准得到的第一次划分结果是（　）。

A （40，46，56，38，79，84）

B （40，38，46，79，56，84）

C （40，38，46，56，79，84）

D （84，40，38，46，56，79）

2、【单选题】设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找键值为84的结点时，经（　）次比较后查找成功。

A 2

B 3

C 4

D 12

3、【单选题】最小生成树的构造可使用（　）。

A prim算法

B 冒泡算法

C 迪杰斯特拉算法

D 哈夫曼算法

4、【单选题】使用折半查找，线性表必须（　）。

A 以顺序方式存储

B 以链式方式存储，且元素已按值排好序

C 以链式方式存储

D 以顺序方式存储，且元素已按值排好序

5、【单选题】在一棵二叉树中，第5层上的结点数最多为（　）。

A 8

B 15

C 16

D 32

6、【单选题】若一个栈的输入序列是1，2，3，……，m，输出序列的第一个元素是m，则第ｉ个输出元素是（　）。

A m - i

B m – i + 1

C i

D 不确定

7、【单选题】下列陈述中正确的是（　）。

A 二叉树是度为2的有序树

B 二叉树中结点只有一个孩子时无左右之分

C 二叉树中必有度为2的结点

D 二叉树中最多只有两棵子树，并且有左右之分

8、【单选题】在一个具有k个结点的无向图中，要连通全部结点至少需要（　）。

A k条边

B k+1条边

C k-1条边

D k/2条边

9、数据结构中，与所使用的计算机无关的是数据的（   ）。

A.物理结构

B.逻辑结构

C.物理和存储结构

D.存储结构

10、研究数据结构就是研究（   ）。

A.数据的存储结构

B.数据的逻辑结构和存储结构

C.数据的逻辑结构和存储结构以及其数据在运算上的实现

D.数据的逻辑结构

单选题，每题10分，共100分

1、在数据结构中，从逻辑上可以把数据结构分成（   ）。

A.紧凑结构和非紧凑结构

B.内部结构和外部结构

C.动态结构和静态结构

D.线性结构和非线性结构

2、数据结构是一门研究计算机中（   ）对象及其关系的科学。

A.集合

B.数值运算

C.非集合

D.非数值运算

3、设有如下遗产继承规则：丈夫和妻子可以互相继承遗产，子女可以继承父亲和母亲的遗产，子女间不能相互继承，则表示该遗产继承关系最合适的数据结构应该是（   ）结构。

A.图状

B.线性

C.树形

D.集合

4、算法的时间复杂度与（    ）有关。

A.所使用的计算机

B.算法本身

C.数据结构

D.算法的程序设计

5、若让元素1，2，3依次进栈，则出栈顺序不可能为（   ）。

A.3，2，1

B.3，1，2

C.1，3，2

D.2，1，3

6、一个队列的入队序列是1，2，3，4。则队列的输出序列是（   ）。

A.1，4，3，2

B.3，2，4，1

C.1，2，3，4

D.4，3，2，1

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

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

B.先后次序无关紧要

C.同时进行

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

8、判断一个顺序队列（最多元素为m）为空的条件是（   ）。

A.front==rear

B.front==rear+1

C.rear=m

D.rear==m-1

9、判断栈满（元素个数最多n个）的条件是（   ）。

A.top==0

B.top!=0

C.top==n-1

D.top=-1

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

A.堆栈

B.线性表

C.队列

D.数组

单选题，每题10分，共100分

1、设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（）排序法。

A.堆排序

B.冒泡排序

C.基数排序

D.快速排序

2、对数据元素序列（49，72，68，13，38，50，97，27）进行排序，前三趟排序结果时的结果依次为第一趟：49，72，68，13，38，50，97，27；第二趟：49，68，72，13，38，50，97，27；第三趟：13，49，68，72，38，50，97，27。该排序采用的方法是（   ）。

A.冒泡排序法

B.插入排序法

C.选择排序法

D.堆排序法

3、一组记录的关键字序列为（47，80，57，39，41，46），利用堆排序（堆顶元素是最小元素）的方法建立的初始化堆为（    ）。

A.39，41，46，80，47，57

B.41，39，46，47，57，80

C.39，80，46，47，41，57

D.39，47，46，80，41，57

4、下述几种排序方法中，要求内存量最大的是（    ）。

A.插入排序

B.选择排序

C.归并排序

D.快速排序

5、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（    ）。

A.2n

B.2n-1

C.n

D.n-1

6、对n个元素进行冒泡排序，通常要进行n-1趟冒泡，在第j趟冒泡中共要进行（     ）次元素间的比较。

A.n-j

B.n-j-1

C.j-1

D.j

7、用某种排序方法对线性表（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.归并排序

8、对具有n个元素的任意序列采用插入排序法进行排序，排序趟数为（　　）。

A.n

B.log2n

C.n+1

D.n-1

9、链表不具备的特点是（   ）。

A.不必事先估计存储空间

B.插入、删除不需要移动元素

C.可随机访问任一结点

D.所需空间与其长度成正比

10、向一个有127个元素的顺序表中插入一个新元素，并保持原来的顺序不变，平均要移动（   ）个元素。

A.7

B.63

C.63.5

D.8

单选题，每题10分，共100分

1、【单选题】堆排序是一种（　）排序。

A 插入

B 选择

C 交换

D 归并

2、【单选题】将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（　）。

A 99

B 98

C 48

D 50

3、【单选题】具有m个结点的无向图的边数最多为（　）。

A m+1

B m（m-1）/2

C m（m+1）

D 2m（m+1）

4、【单选题】链栈与顺序栈相比，比较明显的优点是（　）。

A 插入操作更加方便

B 删除操作更加方便

C 不会出现下溢的情况

D 不会出现上溢的情况

5、【单选题】数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为（　）。

A 索引存储方法

B 顺序存储方法

C 链式存储方法

D 散列存储方法

6、【单选题】在一个单链表中，若P所指结点不是最后结点，在P之后插入S所指结点，则执行（　）。

A S->next=P->next；P->next=S；

B P->next=S->next；S->next=P；

C P->next=P；P->next=S；

D P->next=S；S->next=P；

7、【单选题】由4个结点构造出的不同的二叉树个数共有（　）。

A 8

B 10

C 12

D 14

8、【单选题】已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJGK，则该二叉树根的右子树的根是（　）。

A E

B F

C G

D J

9、【单选题】在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p，q之间插入s结点，则执行的操作是（　）。

A s->next=p->next;p->next=s;

B q->next=s;s->next=p;

C p->next=s->next;s->next=p;

D p->next=s;s->next=q;

10、【单选题】数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为（　）。

A 索引存储方法

B 顺序存储方法

C 链式存储方法

D 散列存储方法