数据结构试题A09-10-1)-张广梅(16K).doc

《数据结构试题A09-10-1)-张广梅(16K).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2009-2010学年第1学期《数据结构》试题（卷）A课程代码BB002016考试方式闭卷考试时长100分钟姓名　学号　　教学班号　　专业级班题号一二三四五六七八合计满分20103040100得分阅卷人注意：选择题、判断题的解答，必须写在答题纸上，答在其它地方的不记分得分答题纸一、选择题（20分）1234567891011121314151617181920得分二、判断题（10分）(对的打“√”，错的画“×”)123456789102009-2010学年第1学期《数据结构》试题（卷）A课程代码BB002016考试方式闭卷考试时长100分钟姓名　学号　　教学班号　　专业级班题号

2、一二三四五六七八合计满分20103040100得分阅卷人注意：选择题、判断题的解答，必须写在答题纸上，答在其它地方的不记分得分一、选择题：（20分，每题1分）1.计算机算法指的是（）A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法2.在下面的程序段中，对x的赋值语句的频度为（）FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)3.以下数据结构中，（）是非线性数据结构A．树B．字符串C．队D．栈4.线性表是具有n个（）的有限序列（n>0）。A．表元素B．字符C．数据元素D．数据项E．信息项5.线性

3、表采用链式存储时，其地址()A．部分地址必须是连续的B．必须占用一片连续的存储单元C．一定不连续D．连续与否均可6.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)7.链表不具有的特点是（）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比8.循环链表H的尾结点P的特点是（）。A．P->NEXT==HB．P->NEXT==H->NEXTC．P==HD．P==H->NEXT9.一个栈的输入序列为123…n，若输出序

4、列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。A.不确定B.n-i+1C.iD.n-i1.有六个元素按6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）A.543612B.453126C.346521D.2341562.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。A.

5、top[2]-top[1]

6、=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]3.栈在（）中应用。A.递归调用

7、B.子程序调用C.表达式求值D.A，Ｂ，Ｃ4.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时()。A．仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改5.设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为()。A.BA+141B.BA+180C.BA+222D.BA+2256.A[1..N，1..N]是对称矩阵，将下三角（包括对角线）以行序存储到一维数组T[N（N+1）

8、/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。A.i（i-1）/2+jB.j（j-1）/2+iC.i（j-i）/2+1D.j（i-1）/2+17.对稀疏矩阵进行压缩存储目的是（）。A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度8.广义表运算式Tail(((a,b),(c,d)))的操作结果是（）。A.(c,d)B.c,dC.((c,d))D.d9.在一棵三叉树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个A．4B．5C．6D．710.n个结点的线索二叉树上含有的线索数为（）A

9、．2nB．n－lC．n＋lD．n11.4．要连通具有n个顶点的无向图，至少需要（）条边。A．n-lB．nC．n+lD．2n得分二、判断题（10分，每题1分）1.线性表的逻辑顺序与存储顺序总是一致的。2.在单链表中，指针p指向元素为x的结点，实现"删除x的后继"的语句是p->next=p->next->next;3.冒泡排序和快速排序都是基于交换两个逆序元素的排序方法。4.取单链表的第i个元素的时间同i的大小有关。5.度为二的树就是二叉树。6.两个串相等的充分必要条件是分配的存储空间一样。7.无向图的邻接