北京外国语大学 数据结构基础 知识要点01-05题目及答案.docx

PAGE1第页

PAGE1

“数据结构基础”知识要点（1）

课程编号：BWCST3001学籍号：____________________

学习中心：________________姓名：____________________

注意事项：1、本试卷满分100分，考试时间120分钟；

本试卷为闭卷考试，请将答案一律写在答题纸上。

单选题（每题2分，共30分）

1.计算机算法必须具备输入、输出和_______等5个特性。

（A）可行性、可移植性和可扩充性

（B）可行性、确定性和有穷性

（C）确定性、有穷性和稳定性

（D）易读性、稳定性和安全性

2.数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：_______

（A）存储结构

（B）逻辑结构

（C）顺序存储结构

（D）链式存储

3.向一个有121个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动_______个元素

（A）8

（B）60.5

（C）61

（D）7

4.线性表Ｌ在_______情况下适用于使用链式结构实现。

（A）需经常修改Ｌ中的结点值

（B）需不断对Ｌ进行删除插入

（C）Ｌ中含有大量的结点

（D）Ｌ中结点结构复杂

5.以下数据结构中哪一个是非线性结构？_______

（A）队列

（B）栈

（C）线性表

（D）二叉树

6.树最适合用来表示_______。

（A）有序数据元素

（B）无序数据元素

（C）元素之间具有分支层次关系的数据

（D）元素之间无联系的数据

7.栈中元素的进出原则是_______

（A）先进后出

（B）后进先出

（C）栈空则进

（D）栈满则出

8.不含任何结点的空树_______。

（A）不是一棵树

（B）是一棵二叉树

（C）是一棵树也是一棵二叉树

（D）既不是树也不是二叉树

9.在一个图中，所有顶点的度数之和等于图的边数的_______倍。

（A）1/2

（B）1

（C）2

（D）3

10.一个栈的入栈序列是a,b,c,d,e,f则栈的不可能的输出序列是_______

（A）fedcba（B）defcba（C）dcefab（D）abcdef

11.一个栈的入栈序列是a,b,c,则栈的不可能的输出序列是_______

（A）cba（B）bca（C）abc（D）cab

12.队列元素的进出原则是_______

（A）先进先出

（B）后进先出

（C）队列空则进

（D）队列满则出

13.具有线性结构的数据结构是（）。

A.图 B.二叉树 C.树 D.队列

14.某算法的语句执行频度为（3n2+nlog2n+n+8）,其时间复杂度表示（）。

A.O(n) B.O(nlog2n) C.O(n2) D.O(log2n)

15.将长度为m的单链表连接在长度为k的单链表之后的算法的时间复杂度为（）。

A.O(1) B.O(k) C.O(m) D.O(m+k)

填空题（每空2分，共20分）

1.设栈s和队列q均为空，先将a，b，c，d，e依次进队列q，再将队列q中顺次出队的元素进栈s，直至队空。再将栈s中的元素逐个出栈，并将出栈元素顺次进队列q，则队列q的状态是______________。

2.数据结构按逻辑结构可分为两大类，它们分别是_____________和______________。

3.线性表的逻辑结构是_____________，其所含元素的个数称为线性表的__________。

4.在具有n个元素的循环队列中，队满时具有______个元素。

5.设循环队列的容量为70，现经过一系列的入队和出队操作后，front为21，rear为10，则队列中元素的个数为___________。

6.两个串相等的充分必要条件是________且对应位置字符相同。

7.树内各结点度的___________称为树的度。

8._________是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

计算题（每题10分，共40分）

1、某不带权有向图如下所示。

给出其邻接矩阵；

该图的出度是多少？

3）该图的入度是多少？

2、分析下面算法（程序段），并计算每个算法的时间复杂度是多少，以及每个算法的最大语句频度以及最大频度的语句是哪句？

1）

2）

3、

请问串的定义是？

A=“Ia