1、本试卷共 12 页第 1 页 本试卷共 12 页第 2 页学院 2009 2010 学年度第二学期数据结构期末试卷 A 卷课程归属部门： 计算机与信息工程学院 试卷适用范围：09 计算机各专业题号 一 二 三 四 五 总分得分1.程序和算法在原则上没有区别，所以在在讨论数据结构时可以通用。 （ ）2.在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 （ ）3.顺序表结构适宜进行顺序存取，而链表适宜进行随机存取。 （ ）4.空栈就是所有元素都为 0 的栈。 （ ）5.队列是限制在两端进行操作的线性表。 （ ）6 串是 n 个字母的有限序列。 （ ）7.树结构中每个结点只有
2、一个直接前驱。 （ ）8.在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。 （ ）9.二叉树的遍历是指按某种顺序访问二叉树中的所有结点。 （ ）10. 带权路径长度最小的二叉树称为哈夫曼树。 （ ）1数据有逻辑结构和 两种结构。2在栈结构中，允许插入、删除的一端称为 。 3设 r 指向单链表的最后一个结点，要在最后一个结点之后插入 s 所指的结点，需执行的三条语句是_；r=s; r-next=null;。4在队列中存取数据应遵循的原则是 。5在一个链队列中，若队首指针为 front，队尾指针 rear，则判断该队列只有一个结点的条件为 。6在空串和空格串中，长度不为 0 的是 。 7
3、在一个具有 n 个单元的顺序栈中，假定以地址高端（即下标为 n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是 top_。8设一棵二叉树结点的先序遍历序列为：ABDECFGH，中序遍历序列为：DEBAFCHG，则二叉树中叶结点是 。9 数据的逻辑结构除了集合以外，还包括线性结构、树形结构和 。10给定如右图二叉树，其前序遍历序列为： 。1算法分析的两个主要方面是（ ） 。A空间复杂性和时间复杂性 B.正确性和简明性C.可读性和文档性 D.数据复杂性和程序复杂性2算法能正确的实现预定功能的特性称为算法的（ ）A健壮性 B易读性 C正确性 D高效性3在具有 n
4、 个结点的单向链表中，实现（ ）的操作，其算法的时间复杂度是 O（n） 。A遍历链表或求链表的第 i 个结点 B.在地址为 P 的结点之后插入一个结点 C. 删除开始结点 D.删除地址为 P 的结点的后继结点4在单链表中，增加头结点的目的是（ ） 。A使单链表至少有一个结点 B标志表中首结点的位置C方便运算的实现 D说明该单链表是线性表的链式存储结构5带头结点的链栈 LS 的示意图如下，栈顶元素是（ ）H A B CLSAH B A CB DC6引起循环队列队头位置发生变化的操作是（ ） 。A. 出队 B.入队 C.取队头元素 D.取队尾元素 7队列 Q，经过下列运算后，再执行 Qempty(
5、Q)的值是（ ） 。InitQueue(Q)(初始化队列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)；ReadQueue(Q,x)；Aa Bb C 0 D1 8串的模式匹配是指（ ） 。A判断两个串是否相等 B. 找某字符在主串中第一次出现的位置C. 对两个串比较大小 D.找某子串在主串中第一次出现在的第一个位置 9设串 S1=“ABCDEFG“,S2=“PQRST“,则ConcatStr(SubStr(S1,2,LenStr(S2),SubStr(S1,LenStr(S2),2)。A. BCDEF B. BCDEFEF C. BCPQRST D. BCD
6、EFG10树最适合用来表示（ ） 。A有序数据元素 B无序数据元素得分 评卷人 一、判断题（每题 1 分，共 10 分）得分 评卷人 二、填空题（每空 2 分，共 20 分）得分 评卷人 三、选择题（每题 2 分，共 40 分）院系:_班级:_姓名:_学号:_.密封线AB CE F GH本试卷共 12 页第 3 页 本试卷共 12 页第 4 页C元素之间无联系的数据 D元素之间有分支的层次关系11把一棵树转换为二叉树后，这棵二叉树的形态是（ ） 。A唯一的 B有多种，但根结点都没有左孩子C有多种 D有多种，但根结点都没有右孩子12下列陈述正确的是（ ） 。A二叉树是度为 2 的有序树 B二叉树
7、中结点只有一个孩子时无左右之分C二叉树中必有度为 2 的结点 D二叉树中最多只有两棵子树，且有左右子树之分13二叉树按某种顺序线索化后，任意结点均有指向其前驱和后继的线索，这种说法（ ） 。A正确 B错误 C 不确定 D都有可能 14将一颗有 100 各结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为 1，则编号为 45 的结点的左孩子编号为（ ） 。A 46 B47 C.90 D91 15某二叉树的后序遍历序列为：DABEC,中序遍历序列为：DEBAC,则前序遍历序列为（ ） 。A.ACBED B.DECAB C.DEABC D.CEDBA16. 下列算法的时间复杂度是（ ）
8、.for(i=0;idata=_2_;p=head-next;while(p!=NULL2层次遍历二叉树，其中 Queue *Q，则出队函数为 OutQueue(Q),队空函数为EmptyQueue(Q)，入队函数 EnQueue(Q,data);typedef struct BT int data;struct BT *lchild,*rchild;BT;void LevelOrder(BT *T) Queue *Q,*P;initQueue(Q);if(_1_)printf(“此二叉树为空！“);return;得分 评卷人 四、程序填空题（每小题 5 分，共 20分）if(p=NULL)p
9、rintf(“不存在%d“,x);else _4_;_5_;EnQueue(Q,T);while(_2_)P=_3_;printf(“%c “,p-data);if(_4_)EnQueue(Q,P-lchild);if(P-rchild)_5_;本试卷共 12 页第 5 页 本试卷共 12 页第 6 页3. 假定用一个循环单链表表示一个循环队列，该队列只设一个队尾指针 rear，试填空完成向循环队列中插入一个元素为 x 的结点的函数。typedef struct queuenode / 定义队列的存储结构 int data;struct queuenode *next;qu;InQueue(q
10、u *rear, int x) / 向队列插入元素为 x 的函数 qu *head,*s;s= 1 ;s-data= 2 ;if (rear=NULL) / 循环队列为空，则建立一个结点的循环队列 rear=s; rear-next; else head= 3 ; / 循环队列非空，则将 s 插到后面rear-next= 4 ;rear=s;5 =head;4根据二元组关系画出逻辑图形，并指出它们属于何种数据结构。F=（D，R） ，其中： D=50，25，64，57，82，36，75，55，R=,1 将图 a 中的二叉树转换成森林（2 分） ，2 将图 b 中的森林转换成二叉树并写出中序序列。
11、 （4 分） AB CD E F GHIJ KLAKB DF HCEG I J（图 a） （图 b）3假设用于通信的电文仅由 A、B、C、D、E、F、G、H8 个字母组成，字母在电文中出现的频率分别为 7，19，2，6，32，3，21，10。试为这 8 个字母设计哈夫曼编码。（本小题 4 分） （注：编码时左分枝标记 0，右分枝标记 1）得分 评卷人 五、问答题（共 10 分）本试卷共 12 页第 7 页 本试卷共 12 页第 8 页学院 2009 2010 学年度第二学期数据结构期末试卷 B 卷课程归属部门： 计算机与信息工程学院 试卷适用范围：09 计算机各专业题号 一 二 三 四 五 总
12、分得分1.数据的逻辑结构和数据的存储结构是相同的。 （ ）2.线性表采用顺序存储，必须占用一片连续的存储单元。 （ ）3.将十进制数转换为二进制数是栈的典型应用之一。 （ ）4.一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。 （ ）5.链队列在一定范围内不会出现队满的情况。 （ ）6 如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。 （ ）7.完全二叉树一定是满二叉树。 （ ）8.具有 n 个叶子结点的哈夫曼树共为 2n-1 个结点。 （ ）9.二叉树的遍历是指按某种顺序访问二叉树中的所有结点。 （ ）10. 顺序存储方式的优点是存储密度大，插入、删除
13、效率高。( )1数据结构按逻辑结构可分为线性结构和 。2若内存空间充足， 栈可以不定义栈满运算。 3解决顺序队列“假溢出”的方法是采用 。4 是被限定为只能在表的一端进行插入运算，在另一端进行删除运算的线性表。5在子串的定位运算中，被匹配的主串称为目标串，子串称为 。6对于二叉树来说，第 i 层上至多有 个结点。 7度为 0 的结点称为 结点。8设某二叉树的中序遍历为：DEBAC，后序遍历序列为 EBCAD，则前序遍历序列为： 。9设 r 指向单链表的最后一个结点，要在最后一个结点之后插入 s 所指的结点，需执行的三条语句是_；r=s; r-next=null;。10. 在一个具有 n 个单元
14、的顺序栈中，假定以地址高端（即下标为 n 的单元）作为栈底，以 top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是 top_。1算法的计算量大小称为算法的（ ） 。A现实性 B.难度 C. 时间复杂度 D.效率2非线性结构中的每个结点（ ）A无直接前驱结点 B 只有一个前驱结点和一个直接后继结点C无直接后继结点 D可能有多个直接前驱结点和多个直接后继结点高效性3已知一个顺序存储的线性表，设每个结点占 m 个存储单元，若第一个结点的地址为 B，则第 i 个结点的地址为（） 。AB+(i-1)*m B. B+i*m C. B-i*m D. B+(i+1)*m4下面关于线性表的叙述中，
15、错误的是（ ） 。A顺序表必须占用一片地址连续的存储单元 B顺序表可以随机存取任一元素C链表不必占用一片地址连续的存储单元 D链表可以随机存取任一元素5带头结点的链栈 LS 的示意图如下，栈顶元素是（ ）H A B CLSAH B A CB DC64 个元素按 A，B，C，D 顺序进 S 栈，执行两次 Pop(S,x)运算后，栈顶元素的值是（ ） 。A. A B. B C. C D. D 7队列 Q，经过下列运算后，再执行 Qempty(Q)的值是（ ） 。InitQueue(Q)(初始化队列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)；ReadQueue
16、(Q,x)；Aa Bb C 0 D1 84 个元素按 A，B，C，D 顺序连续进队 Q，则队尾元素是（ ） 。A. A B. B C. C D. D 9串是一种特殊的线性表，其特殊性体现在（） 。得分 评卷人 一、判断题（每题 1 分，共 10 分）得分 评卷人 二、填空题（每空 2 分，共 20 分）得分 评卷人 三、选择题（每题 2 分，共 30 分）院系:_班级:_姓名:_学号:_.密封线本试卷共 12 页第 9 页 本试卷共 12 页第 10 页A. 可以顺序存储 B.数据元素是一个字符 C. 可以链接存储 D.数据元素可以是多个字符10在一棵具有五层的满二叉树中，结点的总数为（ ）
17、。A16 B31 C32 D3311任何一棵二叉树的叶结点在前序、中序、后序遍历中的相对次序（ ） 。A不发生改变 B发生改变 C不能确定 D以上都不对12二叉树的叶结点个数比度为 2 的结点的个数（ ） 。A无关 B相等 C多一个 D少一个13二叉树按某种顺序线索化后，任意结点均有指向其前驱和后继的线索，这种说法（ ） 。A正确 B错误 C 不确定 D都有可能 14将一颗有 100 各结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为 1，则编号为 45 的结点的左孩子编号为（ ） 。A 46 B47 C.90 D91 15某二叉树的后序遍历序列为：DABEC,中序遍历序列为：
18、DEBAC,则前序遍历序列为（ ） 。A.ACBED B.DECAB C.DEABC D.CEDBA16. 下列算法的时间复杂度是（ ）.for(i=0;idatanext=_4_; _5_; p=q-next;2使用递归函数思想实现二叉树的深度， 试完成下列的程序填空。typedef struct BT int data;struct BT *lchild,*rchild;BT;int TreeDepth (BT *T) int ldep,rdep;if(_1_)return 0;else得分 评卷人 四、程序填空题（每题 5 分，共 20 分） ldep=_2_;rdep=_3_;if(_
19、4_)return ldep+1;else_5_;本试卷共 12 页第 11 页 本试卷共 12 页第 12 页3假定用一个循环单链表表示一个循环队列，该队列只设一个队尾指针 rear，试填空完成向循环队列中插入一个元素为 x 的结点的函数。typedef struct queuenode / 定义队列的存储结构 int data;struct queuenode *next;qu;InQueue(qu *rear, int x) / 向队列插入元素为 x 的函数 qu *head,*s;s= 1 ;s-data= 2 ;if (rear=NULL) / 循环队列为空，则建立一个结点的循环队列
20、 rear=s; rear-next; else head= 3 ; / 循环队列非空，则将 s 插到后面rear-next= 4 ;rear=s;5 =head;4根据二元组关系画出逻辑图形，并指出它们属于何种数据结构。C=（D，R ） ，其中： D=1，2，3，4，5，6，R=（1,2）,（2,3）,（2,4）,（3,4）,（3,5）,（3,6）,（4,5）,（4,6）（园括号表示结点之间关系是有向的）3 将图 a 中的二叉树转换成森林（2 分） ，2将图 b 中的森林转换成二叉树并写出中序序列。 （4 分） AB CD E F GHIJ KLAKB DF HCEG I J（图 a） （图 b）3假设用于通信的电文仅由 A、B、C、D、E、F6 个字母组成，字母在电文中出现的频率分别为 6,5,4,3,2,1,试为这 6 个字母设计哈夫曼编码。（本小题 4 分） （注：编码时左分枝标记 0，右分枝标记 1）得分 评卷人 五、问答题（共 10 分）
