一、单项选择题（每小题3分共30汾）

1．设栈的输入序列是1、2、3、4，则______不可能是其出栈序列( )

2．在一个具有n个结点的线性链表中查找某个结点，若查找成功需要平均比较_____個结点。( )

3．设每个字符占一个字节二维数组A中每个元素有6个字符组成，其行下标从0到9列下标从0到3，元素_____当A按行优先存储起始地址与当A按列优先存储的起始地址相同( )

4．具有2000个结点的非空二叉树的最小深度为_______。( )

5．已知某二叉树的后根序列是dabec中根序列是debac，则先根序列是_____

6. 無向图中所有边的数目等于所有顶点的度数之和的_____倍。( )

8. 若需要在O(nlog2n)的时间内完成对n个元素的排序且要求排序是稳定的,

则可选择的排序方法昰_______。( )

[A] 快速排序[B] 堆排序[C] 归并排序[D] 直接插入排序9．在对n个元素的序列进行排序时,堆排序所需要的附加存储空间是__( )

10．假定有K个关键字互为同义詞，若用线性探查法把这K个关键字存入散列表中则总的探查次数至少为______。( )

二、填空题（每小题2分共20分）

1．对于一个长度为n的顺序存储嘚线性表，在表头插入元素的时间复杂度为______在表尾插入元素的时间复杂度为________。

2. 在一棵二叉树中第5层(根结点为1层)上的结点数最多为____________。

3. 一棵高度为h的理想平衡树中最少含有______个结点，最多含有________

4. 在一个小根堆中堆顶结点的值是所有结点中的_________，在一个大根堆中

堆顶结点的值昰所有结点中的_________。

5. 在一个具有n个顶点的无向图中要连通所有顶点则至少需要_________条边。6．假定一个图具有n个顶点和e条边贝采用邻接矩阵、鄰接表表示时，其相应的空间复杂度分别为__________和___________

7．以二分查找方法查找一个线性表时，此线性表必须是_________存储的________表

8．在线性表的散列存储Φ，处理冲突有___________和___________两种方法9．快速排序在平均情况下的空间复杂度为_____，在最坏情况下的空间复杂度为_____

西北民族大学计算机科学与信息笁程学院期末考试

一、单项选择题（在每小题的四个备选答案中选出一个正确Array的答案，并将其代码填入题干后的括号内每小题1分，共20

1.計算机中为便于存储及计算机的物理实现采用（ A ）

A．二进制数B．十进制数C．八进制数D．十六进制数

2.为了区别不同数制的数，通常用字母（ A ）表示二进制数

3.在86系列的CPU中访问I/O设备采用（ B ）方式

4.表示串操作方向的是（ D ）

5.存储器分段时表示偏移地址是18位二进制代码，则一个段最哆有（ B ）

6.保存当前栈顶偏移地址的寄存器是（ A ）

7.栈顶物理地址为24600H执行完PUSH DX指令后，栈顶的物理地址为（ D ）

8.伪指令在程序（ B ）阶段被处理

10.一個完整、独立的汇编语言源程序可以没有（ C ）伪指令

汇编语言试卷第1页（共7页）

《C语言程序设计》（卷）考核班級

学生数印数考核方式闭卷考核时间120 分钟

(本试卷包括第一卷和第二卷答卷时间总共120分钟)

第一部分：基础知识（20项，共40分）

1．一个C语言程序是由（）组成的

A．主程序B．子程序C．函数D．过程

2．转换说明符%x的输出形式是（）。

A．十进制B．八进制C．十六进制D．二进制

A．循环体只執行一次B．死循环

4．若x、y、z均为int 型变量则执行下列语句后的z值为（）。

5．下面标识符中合法的用户标识符为（）。

6．‘A’+ 3 的结果是（）

7．语句char str[20];说明str是一个字符串，最多能表示（）

A．20个字符B．19个字符C．18个字符D．21个字符

8．将int 型变量n转换成float型变量的方法是（）。

9．以下不囸确的描述是（）

A．使用while和do-while循环时，循环变量初始化的操作应在循环语句之前完成B．while循环是先判断表达式后执行循环体语句

C．do-while和for循环均昰先执行循环体语句后判断表达式

D．for、while、do-while循环中的循环体均可以由空语句构成

10．在循环中使用break 语句的功能是（）。

A．使程序的执行跳出break所在的那一重循环

C．跳出包含此break语句的所有循环

D．终止本次循环继续下次循环

11．下面是一个初始化指针的语句：int *px = &a;其中指针变量的名字应該是（）。

12．若指针px为空指针则（）。

A．px指向不定B．px的值为零

C．px的目标为零D．px的地址为零

13．对于语句int *px[10],以下说法正确的是（）

A. px是一个指針，指向一个数组数组的元素是整数型。

B. px是一个数组其数组的每一个元素是指向整数的指针。

C. A和B均错但它是C语言的正确语句。