东北农业大学网络教育学院
数据结构作业题（一）
一、选择题（每题2分，共20分）
1．在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。
A、O(n)
B、O (n/2)
C、O (1)
D、O (n2)
2．带头结点的单链表first为空的判定条件是（）。
A、first == NULL;
B、first->link == NULL;
C、first->link == first;
D、first != NULL;
3．在一棵树中，（）没有前驱结点。
A、分支结点
B、叶结点
C、树根结点
D、空结点
4．在有向图中每个顶点的度等于该顶点的（）。
A、入度
B、出度
C、入度与出度之和
D、入度与出度之差
5．对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）的值除以9。
A、20
B、18
C、25
D、22
6．下列程序段的时间复杂度为（）。
s=0；
for(i=1；i for(j=1；j s+=i*j； A、O (1) B、O (n) C、O (2n) D、O (n2) 7．栈是一种操作受限的线性结构，其操作的主要特征是（）。 A、先进先出 B、后进先出 C、进优于出 D、出优于进 8．假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为（）。 A、(rear-front-1)％n B、(rear-front)％n C、(front-rear+1)％n D、(rear-front+n)％n 9．高度为5的完全二叉树中含有的结点数至少为（）。 A、16 B、17 C、31 D、32 10．如图所示有向图的一个拓扑序列是( ) A、ABCDEF B、FCBEAD C、FEDCBA D、DAEBCF 二、填空题（每空1分，共20分） 1．n (n﹥0) 个顶点的无向图最多有条边，最少有条边。 2．在一棵A VL树中，每个结点的左子树高度与右子树高度之差的绝对值不超过。 3．已知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为。 4．在二叉树的第i层上至多有结点。 为，右孩子结点的编号为，双亲结点的编号为。 6．数据的存储结构被分为、、和四种。 7．假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则树中所含的结点数为个，树的深度为，树的度为。 8．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要条边。 9．在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着、 和的联系。 10．一棵含999个结点的完全二叉树的深度为。 三、运算题（每题5分，共10分） 1．设有一个10 10的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。 2．已知一个有序表( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 顺序存储于一维数组a[12]中，根据折半 四、应用题（每题10分，共50分） 1．设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。 （1）用直接插入排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。 （2）用直接选择排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。 2．判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。 （1）100，85，98，77，80，60，82，40，20，10，66 （2）100，98，85，82，80，77，66，60，40，20，10 （3）100，85，40，77，80，60，66，98，82，10，20 （4）10，20，40，60，66，77，80， 82，85，98，100 3．试找出分别满足下列条件的所有二叉树。 1）先序序列和中序序列相同2）中序序列和后序序列相同 3）先序序列和后序序列相同4）中序序列与层次遍历序列相同 4．设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2，若T中有6个叶结点，试问：（1）T树的最大深度Kmax=?最小可能深度Kmin=? （2）T树中共有多少非叶结点？ (3) 若叶结点的权值分别为1,2,3,4,5,6。请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。 5．一棵有n(n>0)个结点的d度树，若用多重链表表示，树中每个结点都有d个链域，则在表示该树的多重链表中有多少个空链域? 为什么? 储，则A[7,1]和A[2,4]的第一个字节的地址是多少？ 数据结构作业题（二） 一、选择题（每题2分，共20分） 1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）。 A、HL=p; p->next=HL; B、p->next=HL; HL=p; C、p->next=HL; p=HL; D、p->next=HL->next; HL->next=p; 2．由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。 A、24 B、48 C、72 D、53 3．一个数组元素a[i]与（）的表示等价。 A、*(a+i) B、a+i C、*a+i D、&a+i 4．下面程序段的时间复杂度为（）。 for(int i=0; i for(int j=0; j a[i][j]=i*j; A、O(m2) B、O(n2) C、O(m*n) D、O(m+n) 5．数据结构是（）。 A、一种数据类型 B、数据的存储结构 C、一组性质相同的数据元素的集合 D、相互之间存在一种或多种特定关系的数据元素的集合 6．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（）。 A、插入 B、删除 C、排序 D、定位 7．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（）。 A、3，2，6，1，4，5 B、3，4，2，1，6，5 C、1，2，5，3，4，6 D、5，6，4，2，3，1 8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（）。 A、不一定相同 B、都相同 C、都不相同 D、互为逆序 9．图的邻接矩阵表示法适用于表示（）。 A、无向图 B、有向图 C、稠密图 D、稀疏图 10．若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（）。 A、f,c,b B、f,d,b C、g,c,b D、g,d,b 二、填空题（每空2分，共40分） 1．含n个顶点的无向连通图中至少含有条边。 2．若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3的希尔排序，则得到的结果为。 3．一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n)，其数量级表示为。 4．在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为和。 5．快速排序在平均情况下的时间复杂度为，在最坏情况下的时间复杂度为。 6．假定对长度n=50的有序表进行二分查找，则对应的判定树高度为________，判定树中前5层的结点数为________，最后一层的结点数为________。 7．假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则度为3、2、1、0的结点数分别为、、 8．在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为个。 9．数据的逻辑结构被分为、、和四种。 10．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移个元素。 三、应用题（每题10分，共60分） 1．设有5个互不相同的元素a、b、c、d、e，能否通过7次比较就将其排好序？如果能，请列出其比较过程；如果不能，则说明原因。 2．有一随机数组(25,84,21,46,13,27,68,35,20),现采用某种方法对它们进行排序,其每趟排序结果如下, 则该排序方法是什么? 初始:25,84,21,46,13,27,68,35,20 第一趟:20,13,21,25,46,27,68,35,84 第二趟:13,20,21,25,35,27,46,68,84 第三趟:13,20,21,25,27,35,46,68,84 3．请在（）内填入正确的排序方法。 设一数组中原有数据如下：15，13，20，18，12，60。下面是一组由不同排序方法进行一遍排序后的结果。 （）排序的结果为：12，13，15，18，20，60 （）排序的结果为：13，15，18，12，20，60 （）排序的结果为：13，15，20，18，12，60 4．设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2，若T中有6个叶结点，试问：（1）T树的最大深度Kmax=?最小可能深度Kmin=? （2）T树中共有多少非叶结点？ (3) 若叶结点的权值分别为1,2,3,4,5,6。请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。 5．一棵有n(n>0)个结点的d度树，若用多重链表表示，树中每个结点都有d个链域，则在表示该树的多重链表中有多少个空链域? 为什么? 6．有一个二维数组A[0:8,1:5]，每个数组元素用相邻的4个字节存储,存储器按字节编址，假设存储数组元素A[0,1]的第一个字节的地址是0，那么存储数组的最后一个元素的第一个字节的地址是多少？若按行存储,则A[3,5]和A[5,3]的第一个字节的地址是多少？若按列存储，则A[7,1]和A[2,4]的第一个字节的地址是多少？ 数据结构作业题（三） 一、单选题（每题2分，共10分） 1、在长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 2、设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为。 A、O(1) B、O(n) C、O(n2) D、O(log 2n) 3、假定一个顺序队列的队首和队尾指针分别为f和r，则判断队空的条件为。 A、f+1==r B、r+1==f C、f==0 D、f==r 4、由3 个结点可以构造出多少种不同的二叉树。 A、2 B、3 C、4 D、5 5、适用于折半查找的表的存储方式及元素排列要求为。 A、链接方式存储，元素无序B．链接方式存储，元素有序 C、顺序方式存储，元素无序D．顺序方式存储，元素有序 二、填空题（每空1分，共25分） 1、在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着、 和的联系。 2、在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为，若假定p为一个数组a中的下标，则其后继结点的下标为。 3、在初始化一个稀疏矩阵的函数定义中，矩阵形参应说明为参数。 4、栈又称为表，队列又称为表。 5、后缀表达式“4 5 + 3 * 2 4 + * ”的值为。 6、一棵深度为5的满二叉树中的结点数为个，一棵深度为3的满四叉树中的结点数为个。 7、对于一棵含有40个结点的理想平衡树，它的高度为。 8、从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明，若元素的值小于根结点的值，则继续向查找，若元素的值大于根结点的值，则继续向查找。 9、对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为。 10、对于一个具有n个顶点和e条边的连通图，其生成树中顶点数和边数分别为 和。 11、二分查找过程所对应的判定树既是一棵，又是一棵。 12、在归并排序中，进行每趟归并的时间复杂度为，整个排序过程的时间复杂度为，空间复杂度为。 13、给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为__________，带权路径长度WPL的值为__________。 三、运算题（每题6分，共24分） 1、假定一棵普通树的广义表表示为a(b(e),c(f(h,i,j),g),d)，分别写出先根、后根、按层遍历的结果。 先根：。 后根：。 按层：。 2、已知一个带权图的顶点集V和边集G分别为： V = { 0，1，2，3，4，5，6，7}； E = {（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13， （3，5）9，（3，6）10，（4，6）4，（5，7）20 }； 则求出该图的最小生成树的权。 最小生成树的权：。 3、对于线性表（18,25,63,50,42,32,90,66）进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为0的元素有个，散列地址为3的元素有个，散列地址为5的元素有个。 4、假定一组记录的排序码为（46，79，56，38，40，80，25，34），在对其进行快速排序的过程中，对应二叉搜索树的深度为，分支结点数为。 四、阅读算法（第一题7分，第二题8分） 1、void AA(LNode * & HL) { InitList(HL); InsertRear(HL,30); InsertRear(HL,50); int a[5] = {15,8,9,26,12}; for ( int i=0; i<5; i++ ) InsertFront(HL,a[i]); } 该算法被调用执行后，得到的以HL为表头指针的单链表中的数据元素依次为：。 2、void AH(Heap & HBT , const ElemType item) // HBT为一个小根堆 { HBT.heap[HBT.size]=item; HBT.size++; ElemType x=item int i=HBT.size-1; while ( i != 0 ){ int j=(i-1)/2; if ( x>=HBT.heap[j]) break; HBT.heap[i]=HBT.heap[j]; i=j; } HBT.heap[i]=x; } 该算法的功能为：。 五、算法填空，在画有横线的地方填写合适的内容。（12分） 从一维数组A[n]中二分查找关键字为K的元素的递归算法，若查找成功则返回对应元素的下标，否则返回-1。 int Binsch( ElemType A[] , int low , int high , KeyType K ) { if ( low<=high ) { int mid = (low+high)/2; if ( K==A[mid].key) ; else if (K } else return -1; } 六、编写算法（14分） 编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法，若查找成功则由item带回整个结点的值并返回true，否则返回false。 bool Find( BTreeNode * BST , ElemType & item ) 数据结构作业题（四） 一、选择题（每题2分，共20分） 1．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 2．以下数据结构中，哪一个是线性结构（）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 3．连续存储设计时，存储单元的地址（）。 A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 4．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）。 A. O(0) B. O(1) C. O(n) D. O(n2) 5．在双向链表指针p的结点前插入一个指针q的结点操作是（）。 A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q； B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink; C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q; D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q; 6．若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。 7．有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 8．用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 10．栈和队列的共同点是（）。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点 二、填空题（每空2分，共30分） 1．数据结构中评价算法的两个重要指标是和。 2．一个算法具有5个特性: 、、，有零个或多个输入、有一个或多个输出。 3．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。4．对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ______个，单链表为_______个。5．设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为_ _;若以列序为主序顺序存储，则元素a[45,68]的存储地址为_ _。 6．所谓稀疏矩阵指的是_______。 7．广义表的_______ 定义为广义表中括弧的重数。 8．具有256个结点的完全二叉树的深度为______。 9．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶子结点。 10．高度为8的完全二叉树至少有______个叶子结点。 三、计算题（每题6分，共30分） 1．如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6;请说明为什么不能或如何才能得到。 2．假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行先序、中序、后序、按层遍历的结果。 先序： 中序： 后序： 按层： 3．已知一个图的顶点集V和边集G分别为：V={0,1,2,3,4,5,6,7}; E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10, (4,6)4,(5,7)20,(6,7)30}; 按照普里姆算法从顶点0出发得到最小生成树，试写出在生成最小生成树的过程中依次得到的各条边。 ________, ________, ________, ________, ________, ________, ________。 4. 已知一个图的顶点集V和边集G分别为： V={0,1,2,3,4,5,6,7,8}; E={<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,7>,<4,7>,<4,8>,<5,7>,<6,7>,<7,8>}; 若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列（提示：先画出对应的图形，然后再运算）。拓扑序列： 5．假定一组记录的排序码为(46,79,56,38,40,80,25,34)，则对其进行快速排序的第一次划分后的结果为________________。 四、算法填空（10分） 1． 五、编程（10分） 1．设计算法以求解从集合{1..n}中选取k（k<=n）个元素的所有组合。例如，从集合{1..4}中选取2个元素的所有组合的输出结果为：1 2，1 3，1 4，2 3， 2 4，3 4。 数据结构作业题（五） 一、选择题（每题2分，共20分） 1．若需要利用形参直接访问实参，则应把形参变量说明为（）参数。 A指针B引用C值 2．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（）。 A q一>next=p一>next；p一>next=q； B p一>next=q一>next；q=p； C 9一>next=p一>next；p一>next=q； D p一>next=q一>next；q一>next=p； 3．在一个顺序队列中，队首指针指向队首元素的（）位置。 A前一个B后一个C当前 4．向二叉搜索树中插入一个元素时，其时间复杂度大致为（）。 A O（1） B O（1og2n） C O（n） D O（nlog2n） 5．假设有两个串A和B，求B在A中首次出现的位置的操作，我们称为（）。 A.连接 B.模式匹配 C.求子串 D.求串长 6．我们对记录进行排序的目的是（）。 A.分类 B.合并 C.存储 D.查找 7．在最坏的情况下，冒泡排序法的时间复杂度为（）。 A.O(lgn) B.O(nlgn) C.O(n2) D.O(n) 8．广义表(A,B,E,F,G)的表尾是（）。 A.(B, E , F, G) B.( ) C.（A，B，E，F，G) D.（G） 9．线性表如果采用链式存储结构，要求内存中的存储单元的地址（）。 A.必须是连续的 B.部分要求是连续的 C.一定不是连续的 D.可以是连续的，也可以是不连续的 10．在数据结构中，从逻辑结构上，我们可以把数据结构分为（）。 A.线性结构和非线性结构 B.内部结构和外部结构 C.顺序结构和链式结构 D.动态结构和静态结构 二、填空题（每空1分，共25分） 1．数据的逻辑结构被分为、、和四种。 2．对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为，在表尾插入元素的时间复杂度为。 3．在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的、和三项。 4．在广义表的存储结构中，每个结点均包含有个域。 5．当用长度为N的数组顺序存储一个栈时，假定用top = =N表示栈空，则表示栈满的条件为。6．假定一棵三叉树的结点个数为50，则它的最小深度为，最大深度为。 7．在一棵二叉树中，第5层上的结点数最多为。 点中的。 9．在一个具有n个顶点的无向圄中，要连通所有顶点则至少需要条边。 10．假定一个图具有n个顶点和e条边，贝采用邻接矩阵、邻接表和边集数组表示时，其相应的空间复杂度分别为、和。 11．以二分查找方法查找一个线性表时，此线性表必须是存储的表。 12．在索引表中，若一个索引项对应主表中的一条记录，则称此索引为表。 13．快速排序在平均情况下的空间复杂度为，在最坏情况下的空间复杂度为。 三、运算题（每题5分，共20分） 1．假定一个大堆为（56，38，42，30，25，40，35，20），则依次从中删除两个元素后得到的堆为。 2．已知一个图的顶点集V和边集6分别为： V={0，1，2，3，4，5，6，7}； E={（04）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}； 按照克鲁斯卡尔算法得到最小生成材，拭写出在最小生成树中依次得到的各条边。 ，，，，，，。 3．假定一组数据的初始堆为（84，79，56，42，40，46，50，38），请写出在堆排序阶段进行前三次对换和筛运算后数据的排列情况。 数据排列情况：。 4．假定一组记录的徘序码为（46，79，56，38，40，80，36，40，75，66，84，24），对其进行归并排序的过程中，第三趟归并后的结果为：。 四、阅读算法，回答问题（每题5分，共10分） 1．void AA （List＆L） { InitList（L）； InsertRear （L，30）； InsertFront（L，50）； int a [4]={5，8，12，15} for（int i=0；1＜4；i＋＋＝InsertRear（L，a [i]）； } 该算法被调用执行后，得到的线性表L为：。 2．void AF（Queue＆Q） { InitQueue（Q）： int a [4]={5，8，12，15} for（int i一0；i＜4；i斗＋＝Qlnsert（Q，迁6）； QInsert（Q，QDelete（Q））； QInsert（Q，30）； QInsert（Q，QDelete（Q）＋10）； whi1e（！QueueEmpty（Q））cout＜＜QDeleie（Q）＜＜”； } 该算法被调用后得到的输出结果为：。 五、算法填空，在画有横线的地方填写合适的内容（10分） 从一维数组A[n]上进行快速排序的递归算法。 void QuickSort（ElemType A [ ]，int s，int t） { int i=s j=t十1； ElemType x=A[s]； d0｛ do i++；while ；／／填写一个循环条件 do j - - ；while（A [ j ] ．stn＞x．stn）； if（I { ElemType temp = A［i］；A［i］= A［j］；A［j］＝temp；} } while（i＜j）； A[s]=A[j]；A[j]=x； if（s＜i一1）； if（j十1＜t）； } 六、编写算法（15分） 编写一个递归算法，统计并返回以BT为树根指针的二叉树中的叶子结点的个数。int Count（BTreeNode*BT） 东北农业大学网络教育学院 数据结构作业题参考答案 习题一参考答案 一、选择题（每题2分，共20分） 二、填空题（每题1分，共20分） 1．n(n-1)/2；0 2． 1 3．5 4．2i-1 5．2i；2i+1；i/2 6．顺序；链接；索引；散列 7．10；4；3 8．n-1 9．一对一；一对多；多对多 10．10 三、运算题（每题5分，共10分） 1．根据题意，矩阵A中当元素下标I与J满足I≥J时，任意元素A[I][J]在一维数组B中的存放位置为I * (I + 1) / 2 + J，因此，A[8][5]在数组B中位置为 8 * (8 + 1) / 2 + 5 = 41。 四、应用题（每题10分，共50分） 1．答： (1)直接插入排序 第一趟(3)[8,3],2,5,9,1,6 第二趟(2)[8,3,2],5,9,1,6 第三趟(5)[8,5,3,2],9,1,6 第四趟(9)[9,8,5,3,2],1,6 第五趟(1)[9,8,5,3,2,1],6 第六趟(6)[9,8,6,5,3,2,1] (2)直接选择排序（第六趟后仅剩一个元素，是最小的，直接选择排序结束） 第一趟(9)[9],3,2,5,8,1,6 第二趟(8)[9,8],2,5,3,1,6 第三趟(6)[9,8,6],5,3,1,2 第四趟(5)[9,8,6,5],3,1,2 第五趟(3)[9,8,6,5,3],1,2 第六趟(2)[9,8,6,5,3,2],1 2．(1)是大堆；(2)是大堆；（4）是小堆； (3)不是堆，调成大堆100，98，66，85，80，60，40，77，82，10，20 3．答： “左子树—右子树―根＂，根据以上原则，本题解答如下： （1）若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树 （2）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树． （3）若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树． （4）若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树 4．答： （1）T 树的最大深度Kmax=6（除根外，每层均是两个结点） T 树的最小深度Kmin=4（具有6个叶子的完全二叉树是其中的一种形态） （2）非叶子结点数是5。（n2=n0-1） （3）哈夫曼树见下图，其带权路径长度wpl=51 Wpl=4*3+3*3+2*(4+5+6)=51 5．答： n （n>0）个结点的d 度树共有nd 个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nd-(n-1)=n(d-1)+1个。 习题二参考答案 一、选择题（每题2分，共20分） 二、填空题（每空2分，共40分） 1．n-1 2．（15，02，21，24，26，57，43，66，81，48，73） 3．O （n ） 4 5 6 1 2 3 5．O(nlog 2n) ；O(n 2) 6．6； 31； 19 7．2； 1； 1； 6 8． 6 9．集合结构；线性结构；树型结构；图形结构 10．n-i+1 三、应用题（每题10分，共60分） 1．答： 可以做到。取a 与b 进行比较，c 与d 进行比较。设a>b,c>d(ad ，则有序a>b>d ；若b 3．①快速排序 ②冒泡排序 ③直接插入排序 4．答： （1）T 树的最大深度Kmax=6（除根外，每层均是两个结点） T 树的最小深度Kmin=4（具有6个叶子的完全二叉树是其中的一种形态） （2）非叶子结点数是5。（n2=n0-1） （3）哈夫曼树见下图，其带权路径长度wpl=51 Wpl=4*3+3*3+2*(4+5+6)=51 5．答： n （n>0）个结点的d 度树共有nd 个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nd-(n-1)=n(d-1)+1个。 6．答： （1）176 （2）76和108 （3）28和116。 习题三参考答案 一、单选题（每题2分，共10分） 1、A 2、B 3、D 4、D 5、D 二、填空题（每空1分，共25分） 1、1:1 1:N M:N （或者 1对1 1对N M 对N ） 4 5 6 1 2 3 3、引用 4、后进先出先进先出 5、162 6、31 21 7、6 8、查找成功左子树右子树 9、n2 10、n n-1 11、二叉搜索树理想平衡树（次序无先后） 12、O(n) O(nlog2n) O(n) 13、5 96 三、运算题（每题6分，共24分） 1、先根：a,b,e,c,f,h,i,j,g,d; （2分） 后根：e,b,h,i,j,f,g,c,d,a; （2分） 按层：a,b,c,d,e,f,g,h,i,j; （2分） 2、最小生成树的权：55 3、3 1 2 4、5 6 四、阅读算法，回答问题（第一题7分，第二题8分） 1、（12，26，9，8，15，30，50） 2、向HBT堆中插入一个值为item的元素，使得插入后仍是一个堆。 五、算法填空，在画有横线的地方填写合适的内容（12分） return mid return Binsch(A , low , mid-1 , K) return Binsch(A , mid+1 , high , K) 六、编写算法（14分） 评分标准：请根据编程情况酌情给分。 bool Find( BTreeNode * BST , ElemType & item ) { while ( BST != NULL ) { if ( item == BT->data ) { item = BST->data; return true; } else if (item else BST=BST->right; } return false; } 习题1 一、单项选择题 A1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 C2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 D3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 B4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) CA5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。 《数据结构》模拟题（补） 一．单项选择题 1.在线性表的下列存储结构中，读取元素花费时间最少的是【】。 A．单链表B．双链表C．顺序表D．循环链表 2.设计一个判定表达式中左、右括号是否配对出现的算法，采用【】数据结构最佳。 A．集合B．线性表C．队列D．栈 3.n个结点的线索二叉树上含有的线索数为【】。 A．2n B．n-1 C．n D．n+1 4.设广义表D=(a,(b,c)),则tail(D）=【】。 A．b,c B．(b,c) C．((b,c)) D．c 5.由4个结点可以构造出【】种不同的二叉树。 A．12 B．13 C．14 D．15 6.在栈中，出栈操作的时间复杂度为【】。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 7.假设Q[0..len-1]表示循环队列，f为队头指针，r为队尾指针，则进队操作语句是【】。 A．f=f+1 B．r=r+1 C．f=(f+1)%len D．r=(r+1)%len 8.一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为【】。 A．n*n B．n*n/2 C．n*(n+1)/2 D．(n+1)*(n+1)/2 9.队列操作的原则是【】。 A．进优于出B．出优于进C．先进先出D．后进先出 10.下列数据结构中，【】是非线性数据结构。 A．栈B．串C．队列D．树 11.两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【】。 A．p==q B．q->next=p C．p->next=q D．p->next=q->next 12.数组A中，每个元素的长度为4个字节，行下标i从1到5，列下标j从1到4，从首 地址SA开始连续存放在存储器内，该数组按行存放时，元素A[3][2]的起始地址为【】。 A．SA+20 B．SA+36 C．SA+40 D．SA+45 13.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1， 则第i个结点的地址为【】。 A．d1+(i-1)*m B．d1+i*m C．d1+(i+1)m D．d1-i*m 14.分析下列算法suanfa1(n)的时间复杂度是【】。 void suanfa1(int n) { int i,j,x=1； for(i=0；i 东北农业大学网络教育学院 数据结构作业题（一） 一、选择题（每题2分，共20分） 1．在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。 A、O(n) B、O (n/2) C、O (1) D、O (n2) 2．带头结点的单链表first为空的判定条件是（）。 A、first == NULL; B、first->link == NULL; C、first->link == first; D、first != NULL; 3．在一棵树中，（）没有前驱结点。 A、分支结点 B、叶结点 C、树根结点 D、空结点 4．在有向图中每个顶点的度等于该顶点的（）。 A、入度 B、出度 C、入度与出度之和 D、入度与出度之差 5．对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）的值除以9。 A、20 B、18 C、25 D、22 6．下列程序段的时间复杂度为（）。 s=0； for(i=1；i 《数据结构》题库及答案 一、选择题 1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 a. 随机存储； b.顺序存储； c. 索引存取； d. HASH 存取 2．一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4．在一个单链表中，已知p 结点是q 结点的直接前驱结点，若在p 和q 之间插入结点s ，则执行的操作是 。 a. s->nxet=p->next; p->next=s; b. p->next=s->next; s->next=p; c. q->next=s; s->next=p; d. p->next=s; s->next=q; 5．设有两个串p,q ，求q 在p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6．二维数组M 的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7．在线索二叉树中，结点p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1且p->lch=NULL d. 以上都不对 8．在栈操作中，输入序列为（A ，B ，C ，D ），不可能得到的输出序列为：______ A 、（A ， B ， C ， D ） B 、（D ，C ，B ，A ） C 、（A ，C ，D ，B ） D 、（C ，A ，B ，D ） 9．已知某二叉树的后序序列是dabec ，中序序列是debac ，则它的先序序列是 。 A 、acbed B 、decab C 、deabc D 、cedba 10．设矩阵A 是一个对称矩阵，为了节省存储空间，将其下三角部分（见下图）按行序存放在一维数组B[1..n(n-1)/2]中，对任一上三角部分元素)(j i a ij ，在一维数组B 的存放位置是 。 数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C ） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ） A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放 该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。 10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与（ A ）的表示等价。 A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为（ C ） for (int i=0;i 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素 《数据结构》填空作业题答案 第 1 章绪论（已校对无误） 1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。 2．程序包括两个内容：数据结构和算法。 3.数据结构的形式定义为：数据结构是一个二元组：Data Structure =（ D， S）。 4.数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。 5.数据的逻辑结构可以分类为线性结构和非线性结构两大类。 6.在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。 7.在树形结构中，数据元素之间存在一对多的关系。 8.数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。 9.数据的逻辑结构包括线性结构、树形结构和图形结构 3 种类型，树型结构和有向 图结构合称为非线性结构。 10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑 关系由存储单元位置的邻接关系来体现。 11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑 关系由附加的指针域来体现。 12.数据的存储结构可用 4 种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。 13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。 14.数据结构在物理上可分为顺序存储结构和链式存储结构。 15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数 据的实现方法。 16.数据元素可由若干个数据项组成。 17.算法分析的两个主要方面是时间复杂度和空间复杂度。 18.一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂 度是用该算法在运行过程中所占用的存储空间的大小来度量的。 19.算法具有如下特点：有穷性、确定性、可行性、输入、输出。 20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切 的定义，并在有穷时间内计算出结果。 21. 下面程序段的时间复杂度为㏒ 3n 。 1 单选题(每题2分，共20分) 1. 1. 对一个算法的评价，不包括如下(B )方面的内容。 A .健壮性和可读性 B .并行性 C .正确性 D .时空复杂度 2.2. 在带有头结点的单链表HL 中，要向表头插入一个由指针 p 指向 的结点，则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; 都具有相同的(A )。 A.行号 B .列号 C .元素值 D .非零元素个数 9. 快速排序在最坏情况下的时间复杂度为(D )。 A. O(log 2n) B . O(nlog 2n) C . 0(n) D 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致 为 A. O(n) B. O(1) C. O(log 2 n) D. O(n 二、 运算题(每题6分，共24分) 1. 1. 数据结构是指数据及其相互之间的 _________________ 。当结点之 间存在M 对N (M N)的联系时，称这种结构为 __________________________ 。 2. 2. 队列的插入操作是在队列的_ _尾 ________ 行，删除操作是在队 列的 ____ 首 _____ 行。 3. 3. 当用长度为N 的数组顺序存储一个栈时，假定用top==N 表示栈 C. p->next=HL; p=HL; 3. 3. A. C. D. HL=p; p-> next=HL; 对线性表，在下列哪种情况下应当采用链表表示? 经常需要随机地存取元素 B. 表中元素需要占据一片连续的存储空间 一个栈的输入序列为1 2 3， 4. 4. 列的是(C ) A. 2 3 1 C. 3 1 2 AOV 网 是一种(D ) 有向 图 B .无向图 (B ) 经常需要进行插入和删除操作 D.表中元素的个数不变 则下列序列中不可能是栈的输出序 B. 3 2 1 5. 5. 6. .无向无环图 D .有向无环图 采用 开放定址法处理散列表的冲突时，其平均查找长度( B. 高于链接法处理冲突 D .高于二分查找 7. 8. 6. A.低于链接法处理冲突 .与链接法处理冲突相同 7. 参数。 A.值 8. B)。 若需要利用形参直接访问实参时，应将形参变量说明为( B .函数 C .指针 D .引用 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点 9. .0(n 2) (C )。 2 ) 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.35 C. 19 D. 53 图一 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) 习题1 一、单项选择题 1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) 5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 一、单项选择题 1 某算法的时间复杂度是O(n 2 ) ，表明该算法（）。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述，不正确的是（）。 A数据结构相同，对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来，起泡排序属于（）。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是（）。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（）。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按（）方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n（ n≥ 0）个字符的有限（）。其中，n是字符串的长度，表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中，每个数组元素占用 3 个存储单元，从首地址SA 开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为（）。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的长度是（）。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图，其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时，在等概率情况下，搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点（由p 所指向）满足（）。 A p->link==NULL; B P==NULL; 第一章概论 一、选择题 1、研究数据结构就是研究（D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i O(m+n) 6、算法是（D ）。 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（A ）。 i=s=0; while(s 数据结构设计课程代码：7399 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆 1．数据的最小单位是（ A ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．下面关于线性表的叙述错误的是（D）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（C）。 (A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M 4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A）。 (A) BADC(B)BCDA (C) CDAB (D) CBDA 5．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C）。 (A) 9 (B) 10 (C) 11(D) 12 6．下面程序的时间复杂为（B） for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} (A) O(n) (B) O(n2)(C) O(n3) (D) O(n4) 7．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（C）。 (A) q=p->next；p->data=q->data；p->next=q->next；free(q)； (B) q=p->next；q->data=p->data；p->next=q->next；free(q)； (C) q=p->next；p->next=q->next；free(q)； (D) q=p->next；p->data=q->data；free(q)； 8．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C ）。 (A)O(n) (B) O(nlog2n) (C) O(1)(D) O(n2) 9．设一棵二叉树的深度为k，则该二叉树中最多有（D ）个结点。 (A) 2k-1 (B) 2k(C) 2k-1(D) 2k-1 10．设用链表作为栈的存储结构则退栈操作（ B ）。 (A) 必须判别栈是否为满(B) 必须判别栈是否为空 (C) 判别栈元素的类型(D) 对栈不作任何判别 11．函数substr(“DATASTRUCTURE”，5，9)的返回值为（A ）。 (A) “STRUCTURE”(B) “DATA” (C) “ASTRUCTUR”(D) “DATASTRUCTURE” 12．设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（ C）。 (A) N0=N1+1 (B) N0=N l+N2(C) N0=N2+1(D) N0=2N1+l 13．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（B ）。 (A) 空或只有一个结点(B) 高度等于其结点数 (C) 任一结点无左孩子(D) 任一结点无右孩子 14. 深度为k的完全二叉树中最少有（ B ）个结点。 (A) 2k-1-1 (B) 2k-1(C) 2k-1+1(D) 2k-1 数据结构习题集含答案 目录 选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那 么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性 7.算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储 比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12.在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ） 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A ） for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0; 《数据结构》模拟题（开卷） 一、单项选择题 1.分析下列算法suanfa1(n): void suanfa1(int n) { int i,j,x=1； for(i=0；i数据结构习题及参考答案
数据结构试题库答案
数据结构试题及答案(免费)
数据结构模拟题(开卷)
数据结构作业题及参考答案
《数据结构》题库及答案
数据结构试题及答案
数据结构模拟试题及答案
《数据结构》填空作业题(答案)
数据结构试题及答案(10套最新)
《数据结构》模拟试卷一及答案
数据结构习题及参考答案 .
算法与数据结构题库与答案
数据结构试题集(包含答案 完整版)
数据结构模拟试卷(含答案)
数据结构作业(附答案)
数据结构考试题库含答案
数据结构模拟题(开卷)
相关主题
文本预览