数据结构考试习题试卷B

南通大学2006—2007学年第二学期数据结构(闭卷)试卷〔B〕第1页共3页试题一二三四五总分···················装···················装·····················订·························线···················密封线内答题无效学院：专业：班级：学号：。学生姓名〔签名〕：—————————密————————————封——————————线————————得分评卷人一、单项选择题〔每题1分，共20分〕以下各小题的候选答案中只有一个答案是正确的，请把正确答案的字母代号填写在题后括号内。1.下面程序段的时间复杂度为〔〕。1.下面程序段的时间复杂度为〔〕。for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A．O(m2)B．O(n2)C．O(m*n)D．O(m+n)2.以下关于集合说法正确的选项是〔〕。A．集合的元素必须有某种逻辑关系B．集合属于图状结构C．集合作为逻辑结构，结点之间不存在逻辑关系D．集合属于线性结构3.设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，那么数据结构A是〔〕。 A．线性结构 B．树型结构C．图型结构 D．集合4.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动()个元素。A．63.5B．8C．63D．645.带头结点的单链表head为空的判断条件是〔〕。A．head==NULLB．head->next==NULLC．head->next==headD．head!=NULL6.链栈比照顺序栈主要优点在于〔〕。A．通常不会出现栈满的情况B．通常不会出现栈空的情况C．插入操作更加方便D．删除操作更方便7.循环队列SQ采用数组空间SQ．base[0．．n-1]存放其元素值，其头尾指针分别是front和rear，那么当前队列中的元素个数是()。A．(rear-front+n)%nB．(rear-front+1)%nC．(rear-front-1)%nD．(rear-front)%n8.8.二维数组A的每个元素是一个2字节的整数，行下标i的范围从0-8，列下标j的范围从0-9。存放A至少需要的字节数为〔〕A．90B．180C．72D．1449.下面关于串的的表达中，〔〕是不正确的。A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储10.树的后根遍历序列等同于该树对应的二叉树的()。A．先序遍历B．中序遍历C．后序遍历D．层次遍历11.用5个权值为5个叶结点的权值，构造的哈夫曼树共有〔〕个结点。A．14B．11C．10D．912.一棵完全二叉树上有1001个结点,其中叶子结点的个数是〔〕。 A．250B．490C．254D．13.以下图所示的邻接矩阵代表一有向图。在矩阵中，如果第i行第j列的值为1，那么代表第i个结点有一有向边指向第j个结点。在此有向图中，结点3的入度为：()。A．1B．2C14.己知一有向图的邻接表存储结构如以下图所示。那么按深度优先遍历算法从顶点V1出发,所得到的顶点序列为()。A．V1,V2,V3,V5,V4B．Vl,V2,V3,V4,V5C．V1,V3,V4,V5,V2D．V1,V使用班级计51,052,053,054,计师051,软051,052出卷日期2007年6月21日通大学2006—2007学年第二学期数据结构〔闭卷〕试卷〔B〕第2页共3页15.15.以下图所示的拓扑排序的正确结果序列为〔〕。A．516234B．125634C．123456D．52163416.请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做〔〕次关键码比拟。A.2B.3C.417.对包含n个元素的散列表进行检索，平均查找长度为〔〕。A．O(log2n〕B．O(n)C．O(nlog2n)D．不直接依赖于n18.以下不属于散列函数构造方法的是〔〕A．除余法B．平方取中法C．二分法D．随机数法19.排序方法中，从末排序序列中挑选元素，并将其依次放入已排序序列(初始时为空)的一端的方法，称为()。A．希尔排序B．归并排序C．选择排序D．插入排序20.对具有n个元素的任意序列采用选择排序，排序趟数为()。A．n-1B．nC．n+1D．得分评卷人二、判断题〔每题1分，共10分〕请判断下各命题，如正确的，请在前面括号内填上√，否那么填上×。1．〔〕线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。2．〔〕在表结构中最常用的是线性表，栈和队列不太常用。1．〔〕线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。2．〔〕在表结构中最常用的是线性表，栈和队列不太常用。3．〔〕栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。4．〔〕对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。5．〔〕线性表的逻辑顺序与存储顺序总是一致的6．〔〕栈和队列是一种非线性数据结构。7．〔〕栈和队列的存储方式既可是顺序方式，也可是链接方式。8．〔〕两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出时机，应把两个栈的栈底分别设在这片内存空间的两端。9．〔〕对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点.。10．〔〕一个栈的输入序列是12345，那么栈的输出序列不可能是12345。·····················装·····················订·························线························学院：专业：班级：姓名：学号：—————————密————————————封——————————线————————得分评卷人三、填空题(每题1分，共10分)请将以下各题的正确答案填写在空白处。得分评卷人四、应用题〔每题10分，共40分〕请运用所学的数据结构知识解答以下各题。1．设无向图G〔所右以下图所示〕，要求给出该图的深度优先和广度优先遍历的序列，1．设无向图G〔所右以下图所示〕，要求给出该图的深度优先和广度优先遍历的序列，并给出该图的最小生成树。1．1．数据结构中元素间的逻辑关系称为数据的结构。2．最后一个结点的指针域指向头结点的链表称为链表。3．一个栈的输入序列为123…100，假设输出序列的第一个元素是100，输出的第80个元素是___________。4.是限制插入只能在表的一端，而删除在表的另一端进行的线性表。5．散列表的地址区间为0-17,散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是________。6．一个有n个顶点的无向图最多有__________条边。7．有n个结点的完全二叉树，结点序号分别为1，2，…，n，对任意结点i如果存在左孩子，其左孩子结点是________。8．关键路径是指AOE网中从源点到汇点最________的路径。9．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为。10．平衡二叉树中各结点左右子树深度之差的绝对值不超过_______。南通大学2006—2007学年第二学期数据结构〔闭卷〕试卷〔B〕第3页共3页2．设一组初始记录关键字序列为(2．设一组初始记录关键字序列为(45，80，48，40，22，78)，请分别给出前4趟简单项选择择排序和前4趟直接插入排序后的结果。(排序方式为按关键字升序)3．设散列函数为H(k)=k%7,一组关键字为23、14、6、30、12和18,散列表T的地址空间为0-7,用线性探测法解决冲突,试依次将这组关键字插入T中,写出散列表的构造过程,并计算在等概率条件下查找成功的平均查找长度。4．假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用0～7的二进制表示形式是另一种编码方案。对于上述实例，比拟两种方案的优缺点。·······················装·······················订·························线························学院：专业：年级：班级：