数据结构与算法(A卷) 一、填空题（共10题，每题2分，共20分） 1、在计算机科学中，数据是指」 2、队列的插入操作是在队列的 进行，删除操作是在队列的 进行。 3、写出下图中树的各种遍历序列，先序： 后序： M 4、循环队列长度为m,其头、尾指针分别为front和rear,判断队列为空的条件是 ,判断队列为满的条件是 5、假设一个12阶的上三角矩阵A按行优先压缩存储在一维数组B中，则非零元素as.g 在B中的存储位置k= 6、在拓扑排序中，拓扑排序的第一个顶点必定是 的顶点。 7、由6个分别带权值为5,12,9,30,7,16的叶子结点构造一棵Huffman树，该树的 结点个数为 一，带权路径长度为 8、若矩阵中非0元素呈某种规律分布，或存在大量0元素，对这类矩阵实施压缩存储 是为了 9、已知广义表L=(a,b),(c,(d,(e),f),写出 tail(tail(head (L)))= 10、进栈时需将S->top加1，退栈时需将S->top减1。因此，S->top=-1表 示■ ,S->top=stacksize-l表示」 二、选择题（共10题，每题2分，共20分） 1、对于一个栈，如果输入项序列由A、B、C组成，试给出不可能的输出序列为()。 A,ABC B,ACB C,CBA D,CAB 2、假设以数组A[m,n]存放循环队列的元素，其头指针front,当前队列有k个元素，则 队列的尾指针为()。 A,(front+k)mod (n-m+1) B,(m+k)mod n+front C,(front-m+k)mod (n-m+1)+m D,(front-m+k)mod (n-m+1) 3、若用起泡排序法对关键字{(20,17,11,8,6,1}从小到大排序，则须交换的总次数为 ()
数据结构与算法（A 卷） 一、填空题（共 10 题，每题 2 分，共 20 分） 1、在计算机科学中，数据是指 。 2、队列的插入操作是在队列的_________进行，删除操作是在队列的__________进行。 3、写出下图中树的各种遍历序列，先序：____________________后序：______________。 4、循环队列长度为 m，其头、尾指针分别为 front 和 rear，判断队列为空的条件是 ____________,判断队列为满的条件是____________。 5、假设一个 12 阶的上三角矩阵 A 按行优先压缩存储在一维数组 B 中,则非零元素 a8、9 在 B 中的存储位置 k=________________。 6、在拓扑排序中，拓扑排序的第一个顶点必定是___________的顶点。 7、由 6 个分别带权值为 5，12，9，30，7，16 的叶子结点构造一棵 Huffman 树,该树的 结点个数为________,带权路径长度为_________。 8、若矩阵中非 0 元素呈某种规律分布，或存在大量 0 元素，对这类矩阵实施压缩存储 是为了____________________。 9、已知广义表 L=((a,b),(c,(d,(e))),f),写出 tail(tail(head(L)))=_______________。 10、进栈时需将 S–>top 加 1，退栈时需将 S–>top 减 1。因此，S–>top == -1 表 示 ，S–>top =stacksize-1 表示 。 二、选择题（共 10 题，每题 2 分，共 20 分） 1、对于一个栈，如果输入项序列由 A、B、C 组成,试给出不可能的输出序列为（ ）。 A，ABC B，ACB C，CBA D，CAB 2、假设以数组 A[m，n]存放循环队列的元素,其头指针 front,当前队列有 k 个元素,则 队列的尾指针为（ ）。 A，(front+k) mod (n-m+1) B，(m+k)mod n+front C，(front-m+k) mod (n-m+1)+m D，(front-m+k) mod (n-m+1) 3、若用起泡排序法对关键字{20,17,11,8,6,1}从小到大排序,则须交换的总次数为 ( )。 A B C H D I J F K M
A,3 B,6 C,12 D,15 4、对于一个头指针为head的单链表，判定该表为空表的条件是()。 A,head==NULL B,head→next!=NULL C,head→next==NULL D,head!=NULL 5、设无向图的顶点个数为，则该无向图最多有()条边。 A,n-1 B,n(n-1)/2 C,n(n+1)/2 D,n2 6、快速排序在最坏情况下的时间复杂度为()。 A,0(1og2n）B,0(nlog2n） C,0(n) D,0(n2) 7、广义表A满足head(a)=tail(A),则A为() A,() B,() C,(0,0) D,(0,0,0) 8、线性表的链接实现有利于()运算 A,插入操作B,读取操作C,查找操作D,定位操作 9、对一个算法的评价，不包括如下()方面的内容。 A,可读性B,并行性C,正确性D,时空复杂度 10、在有n个叶子结点的哈夫曼树中，其结点总数是()。 A,不确定 B,2nC,2n+1 D,2n-1 三、简答题（共5题，每题5分，共25分） 1、请对下面的无向带权图，写出它的邻接表，并写出按克鲁斯卡尔算法求其最小生成 树的过程。 9 b 6 d 5 3 4 2、使用哈希函数hashf(x)=xMOD11,把一个整数值转换成哈希表下标，现要把数据1， 13,12,34,38,33,27,22插入到哈希表中。写出使用链地址法构造出的哈希表。 3、以关键码序列(503,087,512,061,908,170,897,275,653,426)为例，手 工执行希尔排序算法，写出每一趟排序结束时的关键码状态。排序为增排序，增量为d[1]=5, d[i+1]=d[i]。 4、假设一棵二叉树遍历的先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请画出 该二叉树
A，3 B,6 C，12 D，15 4、对于一个头指针为 head 的单链表,判定该表为空表的条件是( )。 A,head==NULL B,head→next!=NULL C,head→next==NULL D,head!=NULL 5、设无向图的顶点个数为 n，则该无向图最多有( )条边。 A，n-1 B，n(n-1)/2 C，n(n+1)/2 D，n 2 6、快速排序在最坏情况下的时间复杂度为（ ）。 A，O(log2n) B，O(nlog2n) C，0(n) D，0(n2 ) 7、广义表 A 满足 head(A)=tail(A)，则 A 为（ ） A，( ) B，(( )) C，((),()) D，((),(),()) 8、线性表的链接实现有利于（ ）运算 A，插入操作 B，读取操作 C，查找操作 D，定位操作 9、对一个算法的评价，不包括如下（ ）方面的内容。 A，可读性 B，并行性 C，正确性 D，时空复杂度 10、在有 n 个叶子结点的哈夫曼树中，其结点总数是（ ）。 A, 不确定 B, 2n C, 2n+1 D, 2n-1 三、简答题（共 5 题，每题 5 分，共 25 分） 1、请对下面的无向带权图，写出它的邻接表，并写出按克鲁斯卡尔算法求其最小生成 树的过程。 2、使用哈希函数 hashf(x)=x MOD 11,把一个整数值转换成哈希表下标，现要把数据 1， 13，12，34，38，33，27，22 插入到哈希表中。写出使用链地址法构造出的哈希表。 3、以关键码序列（503，087，512，061，908，170，897，275，653，426）为例，手 工执行希尔排序算法，写出每一趟排序结束时的关键码状态。排序为增排序，增量为 d[1]=5， d[i+1]= d[i]。 4、假设一棵二叉树遍历的先序序列为 EBADCFHGIKJ，中序序列为 ABCDEFGHIJK，请画出 该二叉树。 d b c e f g h a 4 3 5 5 5 5 4 9 7 3 6 5 2 6
5、设结点的关键字(key)集合k={26,36,41,15,68,12,6,51,25},以k为权 值集合，构造一棵huffman树，依次取k中各值，构造一棵二叉排序树。 四：算法分析设计题（共3题，第1题15分，第2、3题各10分，共35分） 1、己知两个双向循环链表A和B,它们的元素均按值递增排列。编写算法，将A和B合 并成一个双向循环链表，并使该链表中元素也按值递增排列。以上双向循环链表均带有附设 的头结点。要求：(1)对该算法进行功能注释：(2)填空完成该算法。 Typedef struct node elemType data; Struct node *llink,*rlink: }ListNode; Typedef ListNode *DLinkList: Void merge_dulink(DLinkList ha,DLinkList hb) {P=ha→rlink;q=hb→rlink: ha→llink=ha→rlink=ha; r=ha; while(p!=ha &q!=hb) if(p→data<=q→data) {nextp=p→rlink; P=nextp; } else {nextp=q今rlink: q→rlink=r→rlink; q→11ink=r; r→rlink→1link=q; r→rlink=q: r=q; q=nextq;
5、设结点的关键字（key）集合 k={26，36，41，15，68，12，6，51，25}，以 k 为权 值集合，构造一棵 huffman 树，依次取 k 中各值，构造一棵二叉排序树。 四：算法分析设计题（共 3 题，第 1 题 15 分，第 2、3 题各 10 分，共 35 分） 1、已知两个双向循环链表 A 和 B,它们的元素均按值递增排列。编写算法，将 A 和 B 合 并成一个双向循环链表，并使该链表中元素也按值递增排列。以上双向循环链表均带有附设 的头结点。要求：（1）对该算法进行功能注释；（2）填空完成该算法。 Typedef struct node { elemType data; Struct node *llink,*rlink: }ListNode; Typedef ListNode *DLinkList; Void merge_dulink(DLinkList ha,DLinkList hb) { P=ha→rlink;q=hb→rlink; ha→llink=ha→rlink=ha; r＝ha; while(p!=ha && q!=hb) if(p→data<=q→data) { nextp=p→rlink; _____________; _____________; ______________; ______________; ______________; P=nextp; } else { nextp=q→rlink; q→rlink=r→rlink; q→llink=r; r→rlink→llink=q; r→rlink=q; r=q; q=nextq; }
if(p!=ha) r→rlink=p: p→1links=r; else if (q!=hb) r→rlink=q q→11ink=r; hb→llink→rlink=ha; ha→llink=hb→1link: Free(hb); } 2、试设计一个算法，统计二叉树中叶子结点的个数。 3、试设计一个算法，用于判定一棵给定的二叉树是否为完全二叉树
if(p!=ha) { r→rlink=p； p→llink=r； } else if(q!=hb) { r→rlink=q q→llink=r; hb→llink→rlink=ha; ha→llink=hb→llink； } Free(hb)； } 2、试设计一个算法，统计二叉树中叶子结点的个数。 3、试设计一个算法，用于判定一棵给定的二叉树是否为完全二叉树