数据结构期末考试试卷(通信14).pdf
A卷2 0 1 5 2 0 1 6学年第1学期 数据结构与算法试卷专业班级 通信1401-02姓 名_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _学 号_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _开课系室一计通学院软件工程系考试日期_ _ _ _ _ _ _2015Tl-08_题 号二三四总分得 分阅卷人得分一、填空题(每空1分，共10分)1 .队列的插入操作是在队列的 进行，删除操作是在队列的 进行。2.对于一个长度为n 的单链存储的线性表，在表头插入元素的时间复杂度为，在表尾插入元素的时间复杂度为 o3.设 W 为一个二维数组，其每个数据元素占用4 个字节，行下标i 从。到7,列下标j 从0 到3,则二维数组W 的数据元素共占用 个字节。若按行顺序存放二维数组W,其起始地址为1 0 0,则二维数组元素W的起始地址为4.已知一无向图 G=(V,E),其中 V=a,b,c,d,e E=(a,b),(a,c),(a,d),(e,d),(b,e),(c,d)现从顶点a 开始遍历图。用深度优先遍历，得到的序列是，而用广度优先遍历，得到的序列是。5.对于一棵具有n 个结点的二叉树，用二叉链表存储时，其指针总数为个，其中 个指针是空指针。得分二、单项选择题(每题2分，共20分)1.下列程序段中带有“的语句的执行次数()x=10000;y=0;count=0;while(x=(y+l)*(y+l)count+;y+；A.98 B.99 C.100 D.1012.非空的循环单链表head的尾结点(由p 所指向)满足()。A.p-next=NULL B.p-next=head C.p=NULL D.p=head3.设有a、b、c、d、e、f 等元素依次进入一个空栈，然后出栈。下列顺序不可能是出栈序列的是()oA.abcedfB.abedcfC.fedcbaD.dcefab4.队列操作的原则是（）。A.先进先出 B.后进先出 C.只能进行插入 D.只能进行删除5.已知有向图 G=（V,E）,其中 V=vl,v2,v3,v4,v5,v6,v7,E=,G 的拓扑序列是（）oA.vl,v3,v4,v6,v2,v5,v7 B.vl,v3,v2,v6,v4,v5,v7C.vl,v3,v4,v5,v2,v6,v7 D.vl,v2,v5,v3,v4,v6,v76.深度为k 的二叉树的结点总数最多为（）0A.2k-1 B.2k+1 C.2k-1 D.2k-17.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。A.不发生改变 B.发生改变 C.不能确定 D.以上都不对8.具有五层结点（根的层为1）的平衡二叉排序树至少有（）结点。A.10 B.11 C.12 D.139.若X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则 x 的前驱为（）A.X 的双亲 B.X 的右子树中最左的结点C.X 的左子树中最右结点 D.X 的左子树中最右叶结点1 0.散列表的地址区间为0-16,散列函数为H（K）=K mod 17。采用线性探测法处理冲突，并将关键字序列26,25,72,38,8,18,59依次存储到散列表中。元素 59存放在散列表中的地址是（）。A.8B.9C.10D.11得分 三、应 用 题（每 题 10分，共 4 0 分）1.已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ,中序遍历的结果是KBCDAFHIGJ,试画出这棵二叉树，并保留中间过程。2.某带权有向图如下:（1）试画出它的邻接表表示法示意图。（7 分）（2）根据邻接表表示法示意图试写出它的深度优先搜索序列。（3 分）3.假定用于通信的电文仅由8 个字母c 1,c 2,c 3,c 4,c 5,c 6,c 7,c 8组成,各字母在电文中出现的频率分别为5,2 5,3,6,1 0,1 1,3 6,4O试为这8 个字母设计不等长H uf f m a n 编码，并给出该电文的总长度。4、将以下关键字 23,35,17,28,13,52,27,33,15,19,按照树形选择排序的思想进行排序，排列成非递减序列。(1)给出初始选择树。(4分)(2)输出前2个关键字，画出输出每一个关键字后树的结构。(6分)得分 四、算法设计题(每小题15分，共 30分)注意事项：1.答案卷应字迹清楚、语义确切；2.算法应说明基本思路，考虑下面数据结构的抽象数据类型，应对主要数据类型、变量给出说明，所写算法应结构清晰、简明易懂，应加上必要的注释；3.算法可用(类)C+语言等你所熟悉的高级语言编写。1、试写一算法，对单链表表示的线性表(a0,al,.an-l)实现就地逆置。假设表长大于2。所谓就地指辅助空间应为0(1),单链表定义如下：Ty p edef s t r u ct LNo de E l emTy p e da t a;/数据域s t r u ct Lno de*nex t;/指针域 LNo de,*Link Lis t;函数头定义为：v o id inv er t l ink s t(Link Lis t *hl ink)/逆转以hl ink 为头指针的单链表2、请写出利用栈对二叉树进行中根遍历的非递归算法。t y p edef s t r u ct B iTNo de /c 语言的结点结构TE l emTy p e da t a;s t r u ct B iTNo de*l chil d,*r chil d;/左右孩子指针 B iTNo de,*B iTr ee;
