数据结构 期末考试试卷
数据结构
一、选择题
1.算法具有五个重要特性不包括__D____。
A有穷性B确定性C可行性D易读性2.在数据结构中，从逻辑上可以把数据结构分成____C___。
A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部结构3.一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是_B_____。A110 B108 C100 D120 4.线性表的顺序存储结构是一种____A__的存储结构。
A随机存取B索引存取
C顺序存取D散列存取
5.线性表若采用链式存储结构时，要求内存中可用存储单元的地址____D___。
A必须是连续的B部分地址必须是连续的C一定是不连续的D连续或不连续都可以
6.不带头结点的单链表head为空的判定条件是_A___。
A. head= =NULL
B. head->next= =NULL
C. head->next= =head
D. head!=NULL
7. 带头结点的单链表head为空的判定条件是__B__。
A. head= =NULL
B. head->next= =NULL
C. head->next= =head
D. head!=NULL
8. 非空的循环单链表head的尾结点（由p所指向）满足_C___。
A. p->next= =NULL
B. p= =NULL
C. p->next= =head
D. p= =head
9. 在双向循环链表的p所指结点之后插入s所指结点的操作是
__D__。
A. p->right=s; s->left=p; p->right->left=s; s->right=p->right;
B. p->right=s; p->right->left=s; s->left=p; s->right=p->right;
C. s->left=p; s->right=p->right; p->right=s; p->right->left=s;
D. s->left=p; s->right=p->right; p->right->left=s; p->right=s;
10. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若
在q和p之间插入s结点，则执行_B___。
A. s->next=p->next; p->next=s; D. p->next=s->next; s-
>next=p;
B. q->next=s; s->next=p;
C. p->next=s; s->next=q;
11. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s
所指结点，则执行__B__。
A. s->next=p; p->next=s;
B. s->next=p->next; p->next=s;
C. s->next=p->next; p=s;
D. p->next=s; s->next=p;
12. 在一个单链表中，若删除p所指结点的后续结点，则执行
__A__。
A. p->next= p->next->next；
B. p= p->next; p->next= p->next-
>next；
C. p->next= p->next;
D. p= p->next->next；
13. 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列
是_C___。
A. edcba
B. decba
C. dceab
D. abcde
14. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为
p1，p2，p3，…，pn，若p1=n，则pi为_C___。
A. i
B. n=i
C. n-i+1
D. 不确定
15. 栈结构通常采用的两种存储结构是_A___。
A. 顺序存储结构和链式存储结构
B.散列方式和索引方式
C.链表存储结构和数组
D.线性存储结构和非线性存储结构
16. 判定一个顺序栈ST（最多元素为m0）为空的条件是__B__。
A. top !=0
B. top= =0
C. top !=m0
D. top= =m0-1
17. 判定一个顺序栈ST（最多元素为m0）为栈满的条件是__D__。
A. top！=0
B. top= =0
C. top！=m0
D. top= =m0-1
18. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行
C__ __。
(不带空的头结点)
A.HS—＞next=s;
B. s—＞next= HS—＞next; HS—＞next=s;
C. s—＞next= HS; HS=s;
D. s—＞next= HS; HS= HS—＞next;
19. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删
结点的值，则执行__ D __。(不带空的头结点)
A. x=HS; HS= HS—＞next;
B. x=HS—＞data;
C. HS= HS—＞next; x=HS—＞data;
D. x=HS—＞data; HS=
HS—＞next;
20. 一个队列的数据入列序列是1，2，3，4，则队列的出队时输出
序列是___B_ 。
A. 4，3，2，1
B. 1，2，3，4
C. 1，4，3，2
D. 3，2，4，1
21. 判定一个循环队列QU（最多元素为m0）为空的条件是
__C__。
A. rear - front= =m0
B. rear-front-1= =m0
C. front= = rear
D. front= = rear+1
22. 判定一个循环队列QU（最多元素为m0, m0= =Maxsize-1）为满
队列的条件是_A___。
A. ((rear- front)+ Maxsize)% Maxsize = =m0
B. rear-front-1= =m0
C. front= =rear
D. front= = rear+1
23. 循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分
别是front和rear，则当前队列中的元素个数是__A__。
A. (rear-front+m)%m
B. rear-front+1
C. rear-front-1
D. rear-front
24. 栈和队列的共同点是_C___。
A. 都是先进后出
B. 都是先进先出
C. 只允许在端点处插入和删除元素
D. 没有共同点
25. 二维数组A中，每个元素的长度为3个字节，行下标i从0到7，
列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是__C__。
A. 80
B. 100
C.240
D. 270
26. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，
列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为__B__。
A. SA+141
B. SA+180
C. SA+222
D. SA+225
27. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30
个，则叶子结点数为 B 个。
A．15 B．16 C．17 D．47
28. 深度为5的二叉树至多有__B__个结点。
A. 16
B. 32
C. 31
D. 10
29. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉
树中所包含的结点数至少为_ C ___。
A. 2h
B. 2h-1
C. 2h+1
D. h+1
30. 对一个满二叉树，m个树叶，n个结点，深度为h，则__D__ 。
A. n=h+m
B. h+m=2n
C. m=h-1
D. n=2h-1
31. 如果某二叉树的前根次序遍历结果为stuwv，中序遍历为
uwtvs，那么该二叉树的后序为_C___。
A. uwvts
B. vwuts
C. wuvts
D. wutsv
35. 在线索化二叉树中，t所指结点没有左子树的充要条件是
_B___。
A. t—＞left=NULL
B. t—＞ltag=1
C. t—＞ltag=1且t—＞left=NULL
D. 以上都不对
36. 树最适合用来表示_C___。
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的
数据
37．在一个图中，所有顶点的度数之和等于所有边数的___C_倍。
A. 1/2
B. 1
C. 2
D. 4
38．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_B___倍。
A. 1/2
B. 1
C. 2
D. 4
39．一个有n个顶点的无向图最多有__C__条边。
A. n
B. n(n-1)
C. n(n-1)/2
D. 2n
40．具有4个顶点的无向完全图有__A__条边。
A. 6
B. 12
C. 16
D. 20
41．具有6个顶点的无向图至少应有_A___条边才能确保是一个连通图。
A. 5
B. 6
C. 7
D. 8
42．在一个具有n个顶点的无向图中，要连通全部顶点至少需要___C_条边。
A. n
B. n+1
C. n-1
D. n/2
43．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是__D__。
n B. (n-1)2 C. n-1 D. n2
44．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_A___。
A. n
B. n+1
C. n-1
D. n+e
二、填空题
1. 数据逻辑结构包括线性结构、树形结构和图形结
构三种类型，树形结构和图形结构合称为非线性结
构 。
2. 线性结构中元素之间存在 一对一 关系，树形结构中元素
之间存在 一对多 关系，图形结构中元素之间存在 多对多 关系。
3. 在双链表中，每个结点有两个指针域，一个指向__前驱结点__
__，另一个指向_后驱接点__ __。
4. 向量、栈和队列都是_线性___结构，可以在向量的__任何__位
置插入和删除元素；对于栈只能在_栈顶___插入和删除元素；对于队列只能在__队尾__插入元素和_队头___删除元素。
5. 向一个长度为n 的向量的第i 个元素（1≤i ≤n+1）之前插入一个
元素时，需向后移动_n-i+1___个元素。
6. 向一个长度为n 的向量中删除第i 个元素（1≤i ≤n ）时，需向前
移动__n-i__个元素。
7. 在一个循环队列中，队首指针指向队首元素的__同一个位置
__。
8. 在具有n 个单元的循环队列中，队满时共有_n-1___个元素。
9. 已知二维数组A[m][n]采用行序为主方式存储，每个元素占k 个存
储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是_LOC(A[0][0])+(n*i+j)*k______。
11. 深度为k 的完全二叉树至少有_2k-1___个结点。至多有_2k ___个
结点，若按自上而下，从左到右次序给结点编号（从1开
始），则编号最小的叶子结点的编号是__2k-2+1。
12. 在一棵二叉树中，度为零的结点的个数为n 0，度为2的结点的
个数为 n 2，则有n 0=_n 2+1___。
13. 一棵二叉树的第i （i ≥1）层最多有__2i -1__个结点；一棵有n
（n>0）个结点的满二叉树共有__2┗log 2n ┘__个叶子和_n-2┗log 2n ┘____个非终端结点。
三、画图题
1、假设一棵二叉树的先序序列为EBADCFHGIKJ 和中序序列为
ABCDEFGHIJK。请画出该树。
2、假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为
DCEGBFHKJIA。请画出该树。
3、写出相应的二叉树
1 2 3 4 5 6 7 8 9 10 11 12
（a）
4、写出相应的二叉树
1 2 3 4 5 0 0 0 0 6 7
（b）
5、最优二叉树（赫夫曼树）画出相应的图形以及求出路径长度
例6.19 、6.20
6、森林转化为相应的二叉树，题集P
40
四、编程题
1. 已知一个向量A，其中的元素按值非递减有序排列，编写一个函数
插入一个元素x后保持该向量仍按递减有序排列。
void insert(vector A ,int n,int x)
{
int i,j;
if(x>=A[n]) A[n+1]=x;
else
{
i=1;
while(x>=A[i]) i++;
for(j=n;j>=i;j――) A[j+1]=A[j];
a[i]=x;
n++;
}
}
2．试写一算法，对单链表就地逆置。
void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2
{
p=L->next;q=p->next;s=q->next;p->next=NULL;
while(s->next)
{
q->next=p;p=q;
q=s;s=s->next; //把L的元素逐个插入新表表头
}
q->next=p;s->next=q;A->next=s;
}//LinkList_reverse
3．假设称正读和反读都相同的字符序列为?回文?，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是?回
文?。
int Palindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0
{
InitStack(S);InitQueue(Q);
while((c=getchar()!='@')
{
Push(S,c);EnQueue(Q,c); //同时使用栈和队列两种结构
}
while(!StackEmpty(S))
{
Pop(S,a);DeQueue(Q,b));
if(a!=b) return ERROR;
}
return OK;
}//Palindrome_Test
4．若矩阵A m ×n 中的某个元素a ij 是第i 行中的最小值，同时又是第j 列中的
最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维也纳数组存储矩阵A m ×n ，试编写求出矩阵中所有马鞍点的算法。
void Get_Saddle(int A[m][n])//求矩阵A 中的马鞍点
{
for(i=0;i { for(min=A[i][0],j=0;j if(A[i][j] for(j=0;j if(A[i][j]==min) //判断这个(些)最小值是否鞍点 { for(flag=1,k=0;k if(min if(flag) printf("Found a saddle element!\nA[%d][%d]=%d",i,j,A[i][j]); } }//for }//Get_Saddle 5．请写出利用栈对二叉树进行先根次序遍历的非递归算法。 void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法{ InitStack(S); Push(S,T); //根指针进栈 while(!StackEmpty(S)) { while(Gettop(S,p)&&p) { visit(p->data); push(S,p->lchild); } //向左走到尽头 pop(S,p); if(!StackEmpty(S)) { pop(S,p); push(S,p->rchild); //向右一步 } }//while }//PreOrder_Nonrecursive 6．编写递归算法，计算二叉树中叶子结点的数目。 Int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目 { if(!T) return 0; //空树没有叶子 else if(!T->lchild&&!T->rchild) return 1; //叶子结点 else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数 }//LeafCount_BiTree 7.编写递归算法，将二叉树中所有结点的左、右子树相互交换。 Void Bitree_Revolute(Bitree T)//交换所有结点的左右子树 { T->lchild<->T->rchild; //交换左右子树 if(T->lchild) Bitree_Revolute(T->lchild); if(T->rchild) Bitree_Revolute(T->rchild); //左右子树再分别交换各自的左右子树 }//Bitree_Revolute 8．对以孩子-兄弟链表表示的树编写计算树的深度的算法。 int GetDepth_CSTree(CSTree T)//求孩子兄弟链表表示的树T的深度{ if(!T) return 0; //空树 else { for(maxd=0,p=T->firstchild;p;p=p->nextsib) if((d=GetDepth_CSTree(p))>maxd) maxd=d; //子树的最大深度 return maxd+1; } }//GetDepth_CSTree 9．假设二叉树采用链接存储方式存储，编写一个中序遍历二叉树的非递归函数。 void inorder(btree *b) { btree *stack[m0],*p; int top=0; p=b; do{ while(p!=NULL) { top++; stack[top]=p; p=p->left; } if(top>0) { p=stack[top]; top--; printf(?%d?,p-data); p=p->right; } }while(p!=NULL&&top!=0) } 10.有一个单链表（不同结点的数据域值可能相同），其头指针为 head，编写一个函数计算数据域为x的结点个数。 int cout(head) node *head; { node *p; int n=0; p=head; while(p!=NULL) { if(p->data==x) n++; p=p->next; } return(n); } 11．有一个循环双链表，每个结点由两个指针（right和left）以及关键字(key)构成，p指向其中一结点，编写一个函数从该循环双链表中删除p所指向的结点。 void delnode(p) struct dlist *p; { struct dlist *q,*r; q=p; while(q->right!=p) q=q->right; r=p; while(r->left!=p) r=r->left; q->right=r; r->left=q; free(p); } 2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 一、判断题： 1、力矩分配法中的分配系数、传递系数与外来因素（荷载、温度变化等）有关。（ ） 2、若图示各杆件线刚度i 相同，则各杆A 端的转动刚度S 分别为：4 i , 3 i , i 。（√ ） A A A 3、图示结构EI =常数，用力矩分配法计算时分配系数4 A μ= 4 / 11。（ ） 1 2 3 4 A l l l l 4、图示结构用力矩分配法计算时分配系数μAB =12/，μAD =18/。（√ ） B C A D E =1i =1 i =1i =1 i 5、用力矩分配法计算图示结构，各杆l 相同，EI =常数。其分配系数μBA =0.8，μBC =0.2， μBD =0。（√ ） A B C D 6、单元刚度矩阵反映了该单元杆端位移与杆端力之间的关系。（√ ） 7、单元刚度矩阵均具有对称性和奇异性。（ X ） 8、局部坐标系与整体坐标系之间的坐标变换矩阵T 是正交矩阵。（√ ） 9、结构刚度方程矩阵形式为：[]{}{}K P ?=，它是整个结构所应满足的变形条件。（ X ） 10、矩阵位移法中，等效结点荷载的“等效原则”是指与非结点荷载的结点位移相等。（√ ） 二．选择题 (1)欲使图2－1所示体系的自振频率增大，在下述办法中可采用：（ D ） A．增大质量 m； B．将质量 m 移至梁的跨中位置；C．减小梁的 EI； D．将铰支座改为固定支座。 图2－1 (2)平面杆件结构一般情况下的单元刚度矩阵[]66? k，就其性质而言，是：（ B ） A．非对称、奇异矩阵； B．对称、奇异矩阵； C．对称、非奇异矩阵； D．非对称、非奇异矩阵。 (3)已知图2－3所示刚架各杆 EI = 常数，当只考虑弯曲变形，且各杆单元类型相同时，采用先处理法进行结点位移编号，其正确编号是：（A ） 图2－3 一、判断题(共223小题） 1。结构的类型若按几何特征可分为平面结构和空间结构。(A) 2、狭义结构力学的研究对象是板、壳结构(B)。 3 单铰相当于两个约束。(A) 4、单刚节点相当于三个约束。(A) 5、静定结构可由静力平衡方程确定全部约束力和内力。A 6、超静定结构可由静力平衡方程确定全部约束力和内力B。 7 无多余约束的几何不变体系是静定结构。A 8 三刚片规则中三铰共线为可变体系。B 9 两刚片用一个单铰和一个不通过该铰的链杆组成的体系为静定结构。A 10 两刚片用一个单铰和一个不通过该铰的链杆组成的体系为超静定结构B。 11链杆相当于两个约束。B 12 平面上的自由点的自由度为2 A 13 平面上的自由刚体的自由度为3 A 14 铰结点的特征是所联结各杆可以绕结点中心自由转动。A 15 有多余约束的几何不变体系是超静定结构。A 16 无多余约束的几何可变体系是超静定结构。B 17、无多余约束的几何可变体系是静定结构。B 18刚结点的特征是当结构发生变形时汇交于该点的各杆端间相对转角为零。A 19 三刚片规则中三铰共线为瞬变体系。A 20三个本身无多余约束的刚片用三个不共线的单铰两两相连，则组成的体系为静定结构。A 21 一个刚结点相当于3个约束。 22 一个连接3个刚片的复铰相当于2个单铰。A 23 一个铰结三角形可以作为一个刚片。A 24 一个铰结平行四边形可以作为一个刚片。B 25 一根曲杆可以作为一个刚片。A 26 一个连接４个刚片的复铰相当于2个单铰．B 27 任意体系加上或减去二元体，改变体系原有几何组成性质。B 28 平面几何不变体系的计算自由度一定等于零。B 29 平面几何可变体系的计算自由度一定等于零。B 30 三刚片体系中若有1对平行链杆，其他2铰的连线与该对链杆不平行，则该体系为几何不变体系。A 31 三刚片体系中，若有三对平行链杆，那么该体系仍有可能是几何不变的。B 32 三刚片体系中，若有２对平行链杆，那么该体系仍有可能是几何不变的。A 33 一个单铰相当于一个约束。B 34 进行体系的几何组成分析时，若体系通过三根支座链杆与基础相连，可以只分析体系内部。B 35 三刚片体系中，若有两个虚铰在无穷远处，则该体系一定为几何可变。B 36 有多余约束的体系为静定结构。B 37 静定结构一定几何不变。A 38 超静定结构一定几何不变．A 39 几何不变体系一定是静定结构。B 40几何不变体系一定是超静定结构。B 41力是物体间相互的机械作用。A 42 力的合成遵循平行四边形法则。A 43 力的合成遵循三角形法则。A 44 力偶没有合力。A 45 力偶只能用力偶来平衡。A 46 力偶可以和一个力平衡。B 47 力偶对物体既有转动效应，又有移动效应。B 48 固定铰支座使结构在支承处不能移动也不能转动。B 49 可动铰支座使结构在支承处能够转动，但不能沿链杆方向移动。A 50 结点法求解桁架内力应按照结构几何组成相反顺序来求解。A 51 将一个已知力分解为两个力可得到无数解答。A 52 作用力和反作用力是作用在同一物体上的两个力。B 53 作用力和反作用力是作用在不同物体上的两个力。A 54 两个力在同一轴上的投影相等，此两力必相等 B 55 力偶对平面内任一点的矩等于力偶矩A 56 力偶在坐标轴上的投影的代数和等于零A 57 一个固定铰支座相当于两个约束。A 58三个本身无多余约束的刚片用三个不共线的单铰两两相连，则组成的体系为超静定结构B 59 桁架是“只受结点荷载作用的直杆、铰结体系”。A 60桁架结构的内力有轴力。A 61 拱的合理拱轴线均为二次抛物线。B 62无铰拱属于超静定结构。A 63 三铰刚架和三铰拱都属于推力结构。A 64 简支刚架属于推力结构。B 65 三铰拱属于静定结构。A 66 相同竖向载荷作用下，同跨度拱的弯矩比代梁的弯矩大得多。B 67 桁架结构中，杆的内力有轴力和剪力。B 68 竖向载荷作用下，简支梁不会产生水平支反力．A 69 竖向载荷作用下，拱不会产生水平支反力。B 70 竖向载荷作用下，拱的水平推力与拱高成正比。B 一、选择题（每小题2分，共30分） 1. 数据结构是（ D ）。 A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 2．以下与数据的存储结构无关的术语是（ D ）。 A．链队列 B. 链表 C. 顺序表 D. 栈 3．以下数据结构中，（ A ）是非线性数据结构 A．树 B．字符串 C．队 D．栈 4．一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（B）。 A．98 B．100 C．102 D．106 5．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D ）。 A．插入 B．删除 C．排序 D．查找 6．线性表采用链式存储时，其地址(D )。 A．必须是连续的 B．一定是不连续的 C．部分地址必须连续 D．连续与否均可以 7．线性表是(A )。 A．一个有限序列，可以为空 B．一个有限序列，不可以为空 C．一个无限序列，可以为空 D．一个无限序列，不可以为空 8．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ B ）。 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 9. 若一个栈的输人序列是1，2，3，…，n，输出序列的第一个元素是n，则第k个输出元素是（C ）。 A．k B．n-k-1 C．n-k+1 D．不确定 10.对于队列操作数据的原则是（ A ）。 A. 先进先出 B. 后进先出 C. 先进后出 D. 不分顺序 11. 栈和队列的共同点是（ C ）。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点 12．在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（ A ）。 A．front=front->next B．rear=rear->next C．rear->next=front D．front->next＝rear 13. 空串与空格串（ B ）。 A．相同 B．不相同 C．可能相同 D．无法确定 14. 串与普通的线性表相比较，它的特殊性体现在（C ）。 A．顺序的存储结构 B．链接的存储结构 C．数据元素是一个字符 D．数据元素可以任意 15. 串的长度是指（ B ）。 A.串中所含不同字母的个数 B.串中所含字符的个数 C.串中所含不同字符的个数 D.串中所含非空格字符的个数 二、填空题（每空2分，共20分） 1．线性表、栈和队列，串都是__线性_____结构。 2．数据的基本单位是__数据元素_______________。 3．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_顺序______存储结构。 4．已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为Loc(a1)，那么，第i个元素的存储地址Loc(a i)= Loc(a1)+(i-1)*k 。 5．栈（stack）是限定在表尾进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为__栈顶________，而另一端称为_栈底________。 6．一个循环队列Q中，头指针和尾指针分别为Q.front和Q.rear，且最大队列长度为MaxQSize，则判断队空的条件为 Q.rear==Q.front,判断队满的条件为(Q.rear+1)%MaxQSize==Q.front。队列的长度为 (.rear-Q.front+MaxQSize )%MaxQSize 数据结构期末考试题及标准答案 ————————————————————————————————作者：————————————————————————————————日期： 2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。 s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。 第1题第2题2.图示外伸梁，跨中截面C的弯矩为（ ? m D．17kN m 题7图图（a）图（b）图（c）图（d）位移法典型方程中系数k ij=k ji反映了（） A.位移互等定理 B.反力互等定理 第9题第10题 10.FP=1在图示梁AE上移动，K截面弯矩影响线上竖标等于零的部分为（）．DE、AB段B．、DE段C．AB、BC段D．BC、CD段 二、填空题：（共10题，每题2分，共20分） 两刚片用一个铰和_________________相联，组成无多余约束的几何不变体系。 所示三铰拱的水平推力 第3题机动法作静定结构内力影响线依据的是_____________。 ．静定结构在荷截作用下，当杆件截面增大时，其内力____________。 D处的纵标值y D为_________。 第6题第7题 7.图示结构，各杆EI=常数，用位移法计算，基本未知量最少是_________个。 8.图示结构用力法计算时，不能选作基本结构的是______。 3．用力法计算图示刚架，并绘其M 图，EI D 4m N/m EI 10kN/m A B C D 2EI EI 4m 2m 4m G F EI 10k N /m C F l ql 12 2 G A 一、选择题:（共10题，每小题2分，共20分） 1.A 2.D 3. A 4.D 5.A 6.C 7.D 8.B 9.C 10.C 二、填空题（共10空，每空2分，共20分） 1.不通过此铰的链杆 2. FP/2（→） 3.l θ（↓） 4. 刚体体系虚功原理 5.不变 6.-1/2 7.6 8.（c ） 9.反对称 10.无侧移的超静定结构 三、问答题：（共2题，每小题5分，共10分） 1．图乘法的应用条件是什么？求变截面梁和拱的位移时可否用图乘法？ 答.图乘法的应用条件：1）杆轴线为直线，2）杆端的EI 为常数3）MP 和M 图中至少有一个为直线图形。否。（7分） 2．超静定结构的内力只与各杆件的刚度相对值有关，而与它们的刚度绝对值无关，对吗？为什么？ 答：不对。仅受荷载作用的超静定结构，其内力分布与该结构中的各杆刚度相对值有关；而受非荷载因素作用的超静定结构，其内力则与各杆刚度的绝对值有关。（7分） 四、计算题. （1、2题8分，3题10分，4、5题12分,4题共计50分） 1．图示桁架，求1、2杆的轴力。 解：F N1=75KN ，F N2=2 13 5 KN 2．图示刚架，求支座反力，并绘弯矩图。 解：F Ay =22KN （↓）F Ax =48KN （←）F By =42KN （↑） 最终的弯矩图为： 3．用力法计算图示刚架，并绘其M 图，EI 为常数。 数据结构期中考试试题答案 一、单选题（每小题2分，共8分） 1.在一个长度为n的线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为 C 。 A.n B.n/2 C.(n+1)/2 D.(n-1)/2 2.在一个带附加表头的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行 D 。 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; 3．若让元素A，B，C，D依次入栈，则出栈次序不可能出现 D 种情况。 A.D,C,B,A B.A,D,C,B C.B,A,D,C D.D,A,B,C 4．从一个顺序队列删除元素时，首先需要 B 。 A.前移一位队首指针 B.后移一位队首指针 C.取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素 二、填空题（每空1分，共32分） 1．数据的逻辑结构分为集合、线性、树型、图形四种。 2.函数重载要求参数个数、参数类型或参数次序有所不同。 3．在带附加表头的循环双向链表中，表头附加结点的左指针域指向最后一个结点，最后一个结点的右指针域指向表头附加结点。 4．在以HL为表头指针的带附加结点的单链表和循环单链表中，链表为空的条件分别为 HL->next==NULL 和 HL==HL->next 。 5．在由数组a中元素结点构成的单链表中，删除下标为i的结点后，需要把该结点插入到空闲表的表头，具体操作为 a[i].next=a[1].next 、a[1].next=i 。 6．在由数组a中元素结点构成的单链表中，删除下标为i的结点的后继结点并将被删除结点的下标赋给i时，所进行的操作（需要用一个临时变量p）描述为 p=a[i].next 和 a[i].next=a[p].next;i=p 。 7．在稀疏矩阵的十字链接存储中，每个结点的down指针域指向列 号相同的下一个结点，right指针域指向行号相同的下一个结点。 8．一个广义表中的元素分为单元素和表元素两类。 9．广义表A=((a,(b,(),c),((d),e)))的长度为 1 ，深度为 4 。 10．向一个顺序栈插入一个元素时，首先应 top++ ，然后再将待插入元素放入栈顶位置。 11．对于队列，应在队尾进行插入，在队首进行删除。 12．中缀表达式2+7/(4-1)所对应的后缀表达式为 2 7 4 1 - / + @ 。 13．后缀表达式“10 3 5 4 - * - 1 + 3 2 + -”的值为 3 。 14.一棵二叉树的广义表表示为a(b(c,d),e(f(,g))),则e结点的双亲结点为 a ，孩子结点为 f ，树的深度为 4 。 三、运算题（每小题8分，共24分） 1．假定线性表L=（33,69,78,22,44,88）,i=3,x=34,y=22,则对L进行下列一组操作` ListEmpty(L); false GetElem(L,i); 78 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析： 如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长 2017《数据结构》期末考试试题及答案 《数据结构》期末考试试题及答案 1 ................................................................. 2..试题 1 答案............................................................ 7..《数据结构》期末考试试题及答案 2 ................................................................. 9..试题 2 答案........................................................................ 1.. 4. 《数据结构》期末考试试题及答案 3 ............................................................... 1..6试题 3 答案........................................................................ 2.. 1. 数据结构》期末考试试题及答案 1 单选题（每题 2 分，共 20 分） 1. 栈和队列的共同特点是 （ ）。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接方式存储的队列，在进行插入运算时 （ ）. A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D .头、尾指针可能都要修改 3. 以下数据结构中哪一个是非线性结构？ （ ） A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（io ）, A[2][2]存放 若有18个元素的有序表存放在一维数组 A[19]中，第一个元素放A[1]中, 现进行二分查找，则查找 A [3]的比较序列的下标依次为（ A. 1 ， 2， 3 B. 9， 5， 2， 3 C. 9， 5， 3 D. 9， 4， 2， 3 8. 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O （1） B. O （n ） C. O （ 1 og 2n ） D. O （n2） 9. 对于线性表（ 7， 34， 55， 25， 64， 46， 20， 10）进行散列存储时，若选 用 H （K ）=K %9 作为散列函数，则散列地址为 1 的元素有（ ）个， 位置在 676（10），每个元素占一个空间， 表示用 10 进制表示。 问 A[3][3] （10）存放在什么位置？脚注 （10） 5. A ．688 B ．678 C ． 692 D ． 696 树最适合用来表示 （ ）。 A.有序数据元素 B.无序数据元素 6. C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 二叉树的第 k 层的结点数最多为 （ ）. A ．2-1 B.2K+1 C.2K-1 D. 2k-1 7. 二、判断改错题。 1. 位移法仅适用于超静定结构，不能用于分析静定结构。( × ) 2位移法未知量的数目与结构的超静定次数有关。( × ) .3 位移法的基本结构为超静定结构。( × ) 4. 位移法中角位移未知量的数目恒等于刚结点数。（×） 提示：与刚度无穷大的杆件相连的结点不取为角位移未知量。 1. 瞬变体系的计算自由度一定等零。 2. 有多余约束的体系一定是几何不变体系。 1、三刚片用三个铰两两相联不一定成为几何不变体系。（×） 2、对静定结构，支座移动或温度改变不会产生内力。（×） 3、力法的基本体系不一定是静定的。（×） 4、任何三铰拱的合理拱轴不一定是二次抛物线。（×） 5、图乘法不可以用来计算曲杆。（×） 6、静定结构的影响线全部都由直线段组成。（√） 7、多跨静定梁若附属部分受力，则只有附属部分产生内力。（×） 8、功的互等定理成立的条件是小变形和线弹性。（√） 9、力法方程中，主系数恒为正，副系数可为正、负或零。（√） 10.三个刚片用不在同一条直线上的三个虚铰两两相连，则组成的体系是无多余约束的几何不变体系。( √） 三、选择题。 1. 体系的计算自由度W≤0是保证体系为几何不变的 A 条件。 A.必要 B.充分 C.非必要 D. 必要和充分 1、图示结构中当改变B点链杆方向（不能通过A铰）时，对该梁的影响是（ d ） A、全部内力没有变化 B、弯矩有变化 C、剪力有变化 D、轴力有变化 2、图示桁架中的零杆为（ b ） A 、DC, EC, DE, DF, EF B 、DE, DF, EF C 、AF, BF, DE, DF, EF D 、DC, EC, AF, BF 4、右图所示桁架中的零杆为（ b A 、CH BI DG ,, B 、DG DE ,, C 、AJ BI BG ,, D 、BI BG CF ,, 5、静定结构因支座移动，（ b ） A 、会产生内力，但无位移 B 、会产生位移，但无内力 C 、内力和位移均不会产生 D 、内力和位移均会产生 7、下图所示平面杆件体系为（ b ） A 、几何不变，无多余联系 B 、几何不变，有多余联系 C 、瞬变体系 D 、常变体系 嘉兴学院试卷 2012—2013 学年第1 学期期中考试试卷课程名称：数据结构使用班级：信息11级考试形式：开卷试卷代码： 班级：姓名：学号： 一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题1分，共10分) 1．数据的逻辑结构从形式上可用二元组（D，R）表示，其中R是（ D ）的有限集。 A．算法B．数据元素C．数据操作D．数据关系 2．数据结构课程研究的内容涉及到三个方面的内容，它们分别是数据的逻辑结构、数据的（C）和数据的操作。 A．数据元素B．逻辑结构C．存储结构D．计算方法 3．线性结构的顺序存储结构是一种随机存取的存储结构，而链式存储结构是一种（ A ）的存储结构。 A．顺序存取 B．随机存取 C．索引存取 D．散列存取 4．线性表L在（ B ）情况下，最适合采用链式存储结构来实现算法。 A．不需经常对L进行修改 B．需经常对L进行删除和插入操作 C．需经常修改L中结点值 D．L中结点结构复杂 5．在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度 是（ C ）。 A.O(1) B. O(log2n) C. O(n) D. O(n2) 6．在循环顺序队列中，假设以设置一个计数变量num的方法来区分队列判满和判空的条件，front和rear 分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则下面不是队列判满或判空条件是（ A ）。 A．front==rear B. front= =rear && num==0 C. front= =rear && num>0 D. num= =maxSize 7．一个栈的入栈序列是a, b, c, d, e, 则栈的不可能的出栈序列是（ D ）。 A．abcde B．decba C．edcba D．dceab 8．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（ C ）。 A．top = =0 B.top= =-1 C. top = =maxSize D.top = = maxSize-1 9．设线性表有n个元素，严格说来，以下操作中，（ B ）在顺序表上实现比链表上实现比链表上实现效率更高。 Ⅰ输出第i个（0≤i≤n-1）数据元素的值 Ⅱ交换第3个数据元素与第4个数据元素的值 Ⅲ顺序输出这n个数据元素的值 A．Ⅰ B．Ⅰ、Ⅱ C．Ⅰ、Ⅲ D．Ⅱ、Ⅲ 10. 在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为s,则修改链的Java语句序列 是（ D ）。 A．s.setNext(p); q.setNext(s); B. p.setNext(s.getNext()); s.setNext(p); C. q.setNext(s.getNext()); s.setNext(p); D. p.setNext(s); s.setNext(q); 二、填空题（20分，每空1分） 1．算法的复杂度通常体现为时间复杂度和空间复杂度两个指标。 2．设有函数T (n)=3n2-n+4，T (n)=O ( n2)。 3．要将一个顺序表{a0,a1,……,a n-1}中第i个数据元素a i(0≤i≤n-1)删除，会引起n-1-i个数据元素的移动。 4．队列也是一种操作受限的线性表，它与栈不同的是，队列中所有的插入操作均限制在表的一端进行，而所有的删除操作都限制在表的另一端进行，允许插入的一端称为队尾，允许删除的一端称为队首。队列具有先进先出的特点。 5．在一个单链表中删除p所指结点时，可执行如下操作： q=p.getNext(); p.setData(q.getData());p.setNext( q.getNext() ); 6．设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出栈的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是3。 7．若双向链表的结点类描述为：public class DuLNode { pvivate Object data; private DuLNode piror; private DuLNode next; …… } 则在带头结点的双向链表中的p结点之前插入一个新结点s，其修改指针的java语句序列是： 1）p.getPiror().setNext(s); 2）s.setPiror(p.gettPiror()); 3）s.setNext(p); 4）p.setPiror(s); 8．在不带表头结点的链栈中，栈顶指针top直接指向栈顶元素，如果链栈中结点的类描述为： class Node { 命题人或命题小组负责人签名：所（室、教研部）负责人签名：分院（部）领导签名： 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ c）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（d ）。 for(i=n-1；i>=0；i--) for(j=0；j 广东创新科技职业学院期末考试试题（标明A 卷、B 或C 卷） 2018 —2019 学年第二学期考试科目：《数据结构》 (闭（开）卷 90分钟) 院系____________ 班级____________ 学号___________ 姓名 __________ 一、选择题（每小题 2 分，共 40 分） 1.计算机识别、存储和加工处理的对象被统称为（）。 A ．数据 B ．数据元素 C ．数据结构 D ．数据类型 2.数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括（）三方面内容。 A ．数据的逻辑结构、数据的存储结构、数据的描述 B ．数据的逻辑结构、数据的存储结构、数据的运算 C ．数据的存储结构、数据的运算、数据的描述 D ．数据的逻辑结构、数据的运算、数据的描述3．数据的逻辑结构包括（）。 A ．线性结构和非线性结构 B ．线性结构和树型结构 C ．非线性结构和集合结构 D ．线性结构和图状结构 4.（）的特征是：有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前驱和一个直接后继。 A ．线性结构 B ．非线性结构 C ．树型结构 D ．图状结构 5. 评价一个算法时间性能的主要标准是（）。 A ．算法易于调试 B ．算法易于理解 C ．算法的稳定性和正确性 D ．算法的时间复杂度 6. 下述程序段①中各语句执行频度的和是（）。 s=0; ① for(i=1;i<=i;j++) s+=j; A ．n-1 B ．n C ．2n-1 D ．2n 7. 下面程序段的时间复杂度为（）。 for(i=0;i 数据结构复习题 一、单选题(每小题2分，共12分) 1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL； D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边 C.n(n—1)／2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A．O(n) B．O(1) C．O(n2) D．O(10g2n) 二、填空题(每空1分，共28分) 1．数据的存储结构被分为——、——、——和——四种。 2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。 3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。 4．在一棵高度为h的3叉树中，最多含有——结点。 5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。 8．表示图的三种存储结构为——、——和———。 9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一种遍历时，其时间复杂度为——。 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为——和——· 11．假定对长度n＝144的线性表进行索引顺序查找，并假定每个子表的长度均为，则进行索引顺序查找的平均查找长度为——，时间复杂度为——· 12．一棵B—树中的所有叶子结点均处在——上。 13．每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫做——排序； 每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做——排序。 14．快速排序在乎均情况下的时间复杂度为——，最坏情况下的时间复杂度为——。 三、运算题(每小题6分，共24分) 1．假定一棵二叉树广义表表示为a(b(c，d)，c(((，8)))，分别写出对它进行先序、中序、后序和后序遍历的结果。 先序： 中序； 后序： 2．已知一个带权图的顶点集V和边集G分别为： V＝{0，1，2，3，4，5}；2017年数据结构期末考试题及答案A
结构力学2期末考试复习题
结构力学期末考试题库
最新数据结构期中试卷及答案
数据结构期末考试题及标准答案
结构力学期末考试试题及答案
数据结构期中考试试题答案c语言版本
《数据结构》期末考试题及答案
数据结构复习资料,java数据结构期末考试
2017数据结构期末考试试题及答案
结构力学期末复习题及答案
数据结构期中试卷信息11)2015-1-21 16.12.11
数据结构期末考试试题及答案
《数据结构》期末考试试卷
大学数据结构期末考试试题(有答案)
- 数据结构(C语言版)期末考试复习试题
- 数据结构期末考试试题及答案
- 《数据结构》期末考试题及答案
- 大学数据结构期末考试题(有答案)
- 《数据结构》期末考试试题及答案
- 数据结构期末测试题及答案
- 《数据结构》期末考试试题及答案
- 数据结构期末考试复习试题(整理完的)
- 数据结构期末考试试题含答案
- (完整版)数据结构期末考试试题及答案
- 数据结构期末测试题及答案
- 2020年数据结构期末考试题及答案A
- 数据结构期末考试试题A答案
- (word完整版)2017年数据结构期末考试题及答案A,推荐文档
- 大学数据结构期末考试试题(有答案)
- 数据结构期末考试试题及答案1
- 数据结构期末考试试题A卷
- 数据结构期末考试试题及复习资料
- 数据结构期末考试试题及答案
- 数据结构期末考试试题及答案