长安大学数据结构期末试题

2009年全国硕士研究生入学统一考试

计算机科学与技术学科联考 计算机学科专业基础综合

考试大纲 教育部考试中心

中国学位与研究生教育学会工科工作委员会

目 录

I. 考查目标

II. 考试形式和试卷结构考查范围 III. 考查范围

数据结构 计算机组成原理 操作系统 计算机网络 IV.

试题示例

Ⅰ.考查目标

计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的概念、基本原理和方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。

Ⅱ.考试形式和试卷结构

一、试卷满分及考试时间

本试卷满分为150分，考试时间为180分钟 二、答题方式 答题方式为闭卷、笔试 三、试卷内容结构 数据结构 45分 计算机组成原理 45分

- 1 -

操作系统 35分 计算机网络 25分 四、试卷题型结构

单项选择题 80分（40小题，每小题2分） 综合应用题 70分

Ⅲ.考查范围

数据结构

【考查目标】

1.理解数据结构的基本概念；掌握数据的逻辑结构

“数据结构”期末考试试题

一、单选题(每小题2分，共12分)

1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL；

D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边

C.n(n—1)／2条有向边 D.n(n一1)条有向边

3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n)

C.O(1Ogzn) D.O(n2)

4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48

C． 72 D． 53

5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。

A.整形 B.引用型

数据结构（本科）期末综合练习一（单选题）

单选题

1. 一个数组元素a[i] 与( )的表示等价。

A. *(a+i) B. a+i C. *a+i D. &a+i

2. 若需要利用形参直接访问实参，则应把形参变量说明为( )参数。 A. 指针 B. 引用 C. 传值 D. 常值

3. 下面程序段的时间复杂度为( )。 for(int i=0; i

for(int j=0; j

22

A. O(m) B. O(n) C. O(m*n) D. O(m+n)

4. 执行下面程序段时，执行S语句的次数为( )。 for(int i=1; i<=n; i++)

for(int j=1; j<=i; j++) S;

22

A. n B. n/2 C. n(n+1) D. n(n+1)/2

5. 下面算法的时间复杂度为( )。 int f(unsign

第一部分 选择题(30分)

一、选择题（20分）

1．组成数据的基本单位是（ ）。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量

2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ ）。

(A) 线性结构

(B) 树型结构 (C) 图型结构 (D) 集合

3．数组的逻辑结构不同于下列（ ）的逻辑结构。 (A) 线性表 (B) 栈 (C) 队列 (D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（ ）个。

(A) 2i (B) 2i (C) 2i-1 (D) 2i-1

5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ ）。

(A) p->next=p->next->next (C) p=p->next->next

(B) p=p->next (D) p->next=p

6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ ）。 (A) 6 (B) 4 (C) 3

第一部分 选择题(30分)

一、选择题（20分）

1．组成数据的基本单位是（ ）。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量

2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ ）。

(A) 线性结构

(B) 树型结构 (C) 图型结构 (D) 集合

3．数组的逻辑结构不同于下列（ ）的逻辑结构。 (A) 线性表 (B) 栈 (C) 队列 (D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（ ）个。

(A) 2i (B) 2i (C) 2i-1 (D) 2i-1

5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ ）。

(A) p->next=p->next->next (C) p=p->next->next

(B) p=p->next (D) p->next=p

6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ ）。 (A) 6 (B) 4 (C) 3

您所在位置：数据结构网络教学平台>>> 试卷汇粹>>数据结构试题汇总

一、选择题

第一二章

1．数据结构是一门研究计算机中____对象及其关系的学科。 （1）数值运算 （2）非数值运算 （3）集合 （4）非集合

2．数据结构的定义为(K，R)，其中K是____的集合。 （1）算法 （2）数据元素 （3）数据操作 （4）逻辑结构 3．算法分析的目的是____。 （1） 找出数据结构的合理性 （2） 研究算法中输入和输出的关系 （3） 分析算法的效率以求改进

（4） 分析算法的易懂性和文档性

4．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行___。 （1）s->link=p;p->next=s;

（2）s->link=p->link;p->link=s; （3）s->link=p->link;p=s;

（4）p->link=s;s->link=p;

5．在循环链表中first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是____。

（1）current->link=NULL (2)first->link=current

（3）first=current (

您所在位置：数据结构网络教学平台>>> 试卷汇粹>>数据结构试题汇总

一、选择题

第一二章

1．数据结构是一门研究计算机中____对象及其关系的学科。 （1）数值运算 （2）非数值运算 （3）集合 （4）非集合

2．数据结构的定义为(K，R)，其中K是____的集合。 （1）算法 （2）数据元素 （3）数据操作 （4）逻辑结构 3．算法分析的目的是____。 （1） 找出数据结构的合理性 （2） 研究算法中输入和输出的关系 （3） 分析算法的效率以求改进

（4） 分析算法的易懂性和文档性

4．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行___。 （1）s->link=p;p->next=s;

（2）s->link=p->link;p->link=s; （3）s->link=p->link;p=s;

（4）p->link=s;s->link=p;

5．在循环链表中first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是____。

（1）current->link=NULL (2)first->link=current

（3）first=current (

一、单项选择题

1、在以下的叙述中，正确的是( A )。 A. 线性表的线性存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C. 栈的操作方式是先进先出 D. 队列的操作方式是先进后出

2、判定一个循环队列qu(最多元素为m0)为空的条件是( A )。 A. qu->front==qu->rear B. qu->front!=qu->rear C. qu->front=(qu->rear+1)%m0 D. qu->front!=(qu->rear+1)%m0

3、向一个栈顶指针为hs的链栈中插入一个s所指结点时，则执行( C )。 A. hs->next=s;

B. s->next=hs->next;hs->next=s; C. s->next=hs;hs=s; D. s->next=hs;hs=sh->next

4、串是一种特殊的线性表，其特殊性体现在（ B ）。 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元

第一章概论 自测题答案

一、填空题

1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。

2. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。

3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。

5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。

6． 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 没有 后续结点，其余每个结点有且只有1个后续结点。

7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。

8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。

第一章概论 自测题答案

一、填空题

1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。

2. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。

3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。

5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。

6． 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 没有 后续结点，其余每个结点有且只有1个后续结点。

7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。

8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。