韩山师范学院2018年本科插班生考试试卷
计算机科学与技术 专业 数据结构 试卷（A 卷）
一、单项选择题（每题2分，共30分）
1. 数据的最小单位是（ B ）。 A. 数据元素 B.数据项 C.数据类型 D. 数据变量
2. 一个栈的输入序列为A B C ，则下列序列中不可能是栈的输出序列的
是( C )。
A. B C A
B.C B A
C. C A B
D. A B C 3．程序段s=i=0；do {i=i+1； s=s+i ；}while(i<=n)；的时间复杂度为（ A ）。 A. O(n)
B. O(nlog 2n)
C.O(n 2)
D.O(n 3/2)
4．一个非空广义表的表头（ D ）。
A.不可能是子表
B.只能是子表
C.只能是原子
D.可以是子表或原子
5．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F 和R ，头指针F 总是指向队头元素的前一位置，尾指针R 总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ D ）。
A. R-F
B.F-R
C. (F-R+M)％M
D. (R-F+M)％M
6．设指针变量p 指向单链表中结点A ，若删除单链表中结点A ，则需要修改指针的操作序列为（ C ）。 A. q=p->next ；p->next=q->next ；free(q)； B. q=p->next ；p->data=q->data ；free(q)；
C. q=p->next ；p->data=q->data ；p->next=q->next ；free(q)；
D. q=p->next ；q->data=p->data ；p->next=q->next ；free(q)；
7．设有一个二维数组A [m ][n ]，假设A [0][0]存放位置在644(10)，A [2][2]存放位置在676(10)，每个元素占一个空间，问A [3][3](10)存放在什么位置？脚注(10)表示用10进制表示（ B ）。
A. 696
B. 692
C.688
D. 678
//c,对的.676+(676-644)/2
A[2][2]与A[0][0] 相差两排零2个元素
A[3][3]与A[2][2] 相差一排零1个元素
因为元素的地址是连续的
所以A[2][2]与A[0][0] 的地址差是A[3][3]与A[2][2]地址差的2倍
A[2][2]与A[0][0] 的地址差是676-644
A[3][3]与A[2][2]地址差是(676-644)/2
所以A[3][3]的地址是676+(676-644)/2
8．设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( D )。
A. 15，10，14，18，20，36，40，21
B.10，15，14，18，20，40，36，21
C. 10，15，14，20，18，40，36，2l
D. 10，15，14，18，20，36，40，21
9．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C）。
A.9
B. 10
C.11
D. 12
10．数组的逻辑结构不同于下列（A）的逻辑结构。
A. 树
B. 栈
C. 队列
D. 线性表
11．根据二叉树的定义可知二叉树共有（B）种不同的形态。
A.4
B. 5
C. 6
D. 7
12．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（A）。
A.head==0
B. head->next==0
C. head->next==head
D.head!=0
//
注意：不论是带头结点的链表还是不带头结点的链表，头指针head都指向链表中的第一个结点。如果该链表有头结点，则头指针head指向头结点，如果没有头结点，则头指针head指向链表的第一个节点。
1 带头结点的单链表中头指针head指向头结点，头结点的值域不含任何信息，从头结点的后继结点开始存储信息。头指针head始终不等于NULL，head->next等于NULL的时候链表为空。
2 不带头结点的单链表中的头指针head直接指向开始结点，当head等于NULL的时候链表为空。
头结点的存在，使得空链表与非空链表的处理变得一直，也方便了对链表的开始结点插入或删除操作。
13．设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（B）。
A.第i行非0元素的个数之和
B. 第i列非0元素的个数之和
C.第i行0元素的个数之和
D. 第i列0元素的个数之和14．设无向图G中有n个顶点，则该无向图的最小生成树上有（C ）条边。
A. 2n
B. 2n-1
C. n-1
D. n
15.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（D）
A. 24
B. 48
C. 53
D. 71
二、填空题（每空2分，共20分）
1．数据的物理结构主要包括_顺序储存结构_和___链式存储结构_两种情况。
2.设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为___N0-1______；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_______个空指针域。
3.设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为：
1) s->next=__p->next____；2) p->next=s；3) t=p->data；
4) p->data=____s_______；5) s->data=t；
4. 已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输
出序列是13452 ，BFS遍历的输出序列是13245
//
深度优先是从某个顶点出发，访问完后，寻找一个未访问的邻接顶点继
续深度优先，如果此路不同就往回退，所以看邻接表，首先访问V1，完了后顺链寻找没有访问的邻接顶点，自然链表中的第一个结点就是v3，接着转到v3再来深度优先，访问v3后，在其链表中第一个邻接顶点是v4
接着访问v4，下面走不通，回到v3，继续顺链往后，自然是v5，v5的邻接顶点中v2还没有访问
所以序列为v1, v3, v4, v5, v2
再看广度优先，从某个顶点完成后，需要一口气将其邻接未访问的所有顶点都访问，后面类推
于是过程是先v1，再顺链将v3，v2依次访问完，然后再依次访问v3和v2的各个未访问邻接顶点，v3链表中顺链可以访问v4，v5，所以最后访问序列为v1, v3, v2, v4, v5
5. 解决散列表冲突的两种方法是___开放定址法____和__链地址法__。
三、判断题（对的划√，错的划×。每小题1分，
共10分）
（×）1．调用一次深度优先遍历可以访问到图中的所有顶点。（×）2.设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。
//因为不知道左右孩子。所以如果已知中序，只需要一个前序或者后序就可以确定二叉树了
（√）3．快速排序是排序算法中平均性能最好的一种排序。
（√）4．不论是入队列操作还是入栈操作，在顺序存储结构上都需
要考虑“溢出”情况。
（×）5．线性表中的所有元素都有一个前驱元素和后继元素。（√）6.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。
//分块查找:即又称索引顺序查找,这是顺序查找的一种改进的方法.在此查找法中,除表本身以外,尚需建立一个"索引表",其包含两项内容:关键字项(其值为该字表中最大的关键字)和指针项(指示该字表的第一个记录在表中的位置).所谓分块指的是第二个子表中所有的关键字都比第一个表中的关键字大,同理,第三个字表都大于第二个字表中的所有的关键字..
通常,分块查找的过程需要分两步:先确定待查记录所在的块(字表),然后在块中顺序查找.
（×）7．向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。
（√）8．不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。
（×）9．子串“ABC”在主串“AABCABCD”中的位置为2。（×）10．用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。
四、程序填空题（每个空2分，共10分）
1.下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。
void bubble(int r[n])
{
for(i=1;i<=n-1; i++)
{
for(exchange=0,j=0; j<_____________;j++) if
(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;}
if (exchange==0) return ； } }
2. 如下为二分查找的非递归算法，试将其填写完整。 Int Binsch(ElemType A[ ],int n,KeyType K) {
int low=0;
int high=n-1;
while (low<=high) {
int mid=____________________________；
if (K==A[mid].key) return mid; //查找成功，返回元素的下标
else if (K<[mid].key)
_________________________; //在左子表上继续查找
else __________________; //在右子表上继续查找
}
return -1; //查找失败，返回-1 }
五、分析简答题（共20分）
1．（10分）求AOE 网的关键路径。
关键路径：v0,v1,v4,v3,v6
2.（10分）一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。
六、算法设计题（10分）
1. 设计两个有序单链表的合并排序算法。
数据结构 一、单选题 1. 计算机算法指的是（b ）。 A．程序B．问题求解步骤的描述C．调度方法D．排序方法 2. 以下数据结构中，（a ）个是非线性数据结构。 A．树B．字符串C．队D．栈 3. 对于顺序存储的线性表，访问元素和插入元素的时间复杂度分别为：（c ）。 A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1) 4. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（b ）。 A.p->next=s;s->next=p->next B.s->next=p->next; p->next=s C.p->next=s;p->next=s->next D.p->next=s->next; p->next=s 5. n个顶点的有向图中,含有向边的数目最多为( d ) A．n-1 B．n C．n(n-1)/2 D．n(n-1) 6. 循环队列存储在数组A[0..m]中，则入队时的操作为（ d ） A．rear=rear+1 B．rear=(rear+1)mod(m-1) C．rear=(rear+1)mod m D．rear=(rear+1)mod(m+1) 7. 字符串?ababaabab?的next函数为（d ） A.011232232 B.012341234 C.011122334 D. 011234234 8. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为（ b ）A．9 B．11 C．15 D．不确定 9. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当以列为主序存放时，元素A[5,8]的首地址为（ b ）。A．BA+141 B．BA+180 C．BA+222 D．BA+225 10. n个顶点的带权无向连通图的最小生成树包含(b )个顶点 A．n-1 B．n C．n/2 D．n+1 11．有关二叉树的下列说法正确的是（ b ） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 12．关键路径是AOE网中（ a ）。 A．从源点到汇点的最长路径B．从源点到汇点的最短路径 C．最长回路 D．最短路径（从源点到汇点的所有路径中，经过弧的数目最多的路径） 13．若查找每个记录的概率相等，则在具有n个记录的连续文件中采用顺序查找查找一个记录，其平均查找长度ASL为（c）。 A．(n-1)/2 B．n/2 C．(n+1)/2 D．n 14．就平均性能而言，目前最好的内部排序方法是（d ） A．冒泡排序B．希尔排序C．堆排序D．快速排序 15．已知广义表LS=((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e的运算是（d ）A．head(tail(LS)) B．tail (head (LS) C．head(tail(head(tail(LS)))) D．head(tail(tail (head (LS)))) 17．在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：( a ) A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B. 在第i个结点后插入一个新结点（1≤i≤n）
韩山师范学院2018年本科插班生考试试卷英语专业基础英语试卷（ A卷） https://www.doczj.com/doc/973243837.html,nguage knowledge. Choose one word, phrase or statement that best completes the sentence. （每空1分，共20分） 1. _____ dull he may be, he is certainly a very successful top executive. A. Although B. Whatever C. As D. However 2 Loudspeakers were fixed in the hall so that everyone__ an opportunity to hear the speech. A. ought to have B. must have C. may have D. should have 3. ____ his knowledge and academic background, he is basically stupid. A. But for B. According to C. For all D. Thanks to 4. The moon, being much nearer to the Earth than the Sun, is the ____ cause of the tides. A. principal B. basic C. initial D. elementary 5. It is absolutely essential that William _____ his study in spite of some learning difficulties. A. continue B. continued C. will continue D. continues 6 The reception was attended by ____ members of the local community. A. excellent B. conspicuous C. prominent D. noticeable 7. The party, ____ I was the guest of honor, was extremely enjoyable. A. by which B. for which C. to which D. at which 8. ____ he wanted to go out with his friends at the weekend, he had to stay behind to finish his assignment.
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 .没有共同点
数据结构试卷（五） 一、选择题(30分) 1．数据的最小单位是（）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（）。 (A) 40，50，20，95 (B) 15，40，60，20 (C) 15，20，40，45 (D) 45，40，15，20 3．设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。 (A) 15，25，35，50，20，40，80，85，36，70 (B) 15，25，35，50，80，20，85，40，70，36 (C) 15，25，35，50，80，85，20，36，40，70 (D) 15，25，35，50，80，20，36，40，70，85 4．函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。 (A) “STRUCTURE”(B) “DATA” (C) “ASTRUCTUR”(D) “DATASTRUCTURE” 5．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。 (A) O(log2n) (B) O(1) (C) O(n2) (D) O(n) 6．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为N l，……，度数为m的结点数为Nm，则N0=（）。 (A) N l+N2+……+Nm (B) l+N2+2N3+3N4+……+(m-1)Nm (C) N2+2N3+3N4+……+(m-1)Nm (D) 2N l+3N2+……+(m+1)Nm 7．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 (A) 25 (B) 10 (C) 7 (D) 1 8．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（）。 (A) abedfc (B) acfebd (C) aebdfc (D) aedfcb 9．设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（）。 (A) n-i (B) n-1-i (C) n+1-i (D) 不能确定 10 设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45 为基准而得到一趟快速排序的结果是（）。 (A) 40，42，45，55，80，83 (B) 42，40，45，80，85，88 (C) 42，40，45，55，80，85 (D) 42，40，45，85，55，80 二、填空题(共30分) 1.设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶 指针top2的初值为n，则判断共享栈满的条件是____________________。 2.在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。
韩山师范学院2017年本科插班生考试试卷 英语 专业 英语语法 试卷（A 卷） 一、Choose the correct answer （每题1分，共40分） Direction: Complete the following sentences and then blacken the corresponding letter on the ANSWER SHEET. 1.______ can get a better view of the game than the participants. A. Looker-on B. Lookers-on C. Looker-ons D. Lookers-ons 2. My mother cut the cloth with ______ scissors. A. a B. two C. a couple of D. a pair of 3.______ receives only a small portion of the total amount of the sun’s energy. A . The earth’s surface B. The surface earth C. The surface of earth D. The earth surface 4. Little boys are easily ______. A. taken out B. taken away C. taken in D. taken over 5. The thief ran away as fast as he could ______ the policeman. A. in sight B. within the sight of C. within sight D. at the sight of 6. Prior ______ his departure, he wrote a letter to his mother. A. of B. from C. to D. in 7. ______ classical music, which follows formal European traditions, jazz is a spontaneous and free form. A. In comparison with B. In connection with C. In regard to D. In contrast to 8. The investigators found that more should be done for ______ in India. A. the poor B. a poor C. poor D. those poor 9. A man suffering from a chock should be given ______. A. hot sweet tea B. a hot sweet tea C. the hot sweet tea D. one hot sweet tea 10. Under no circumstances will there be wage control while I am ______ of the government.
一．选择填空：（20个选择题，共40分。） 1. He ___________ like reading the book. A. is B. doesn’t C. don’t D. do 2. —Do you have lunch at 12:00? —___________. A. Yes, I am. B. Yes, I don’t. C. No, I don’t D. No, I do. 3. —___________ is the pen? —Five yuan. A. What B. How C. How much D. How many 4. Tom ___________ his homework at school. A. doesn’t B. doesn’t do C. don’t D. does not 5. —Nice to meet you. —___________. A. How do you do? B. Nice to meet you, too. C. Fine, thanks. D. How are you? 6. His father buys two ___________ shoes for him. A. pair of B. pairs C. pairs of D. a pair of 7. Let’s ____________ volleyball. That _________ good. A. playing, is B. play, sounds C. play, is sound D. To play, sound 8.The man is David Johnson. Johnson is his ____ name and David is his ____name. A. family, first B. first, family C. first, last D. Family,family 9.Do you need shoes___sports? We have lots of shoes ___very
数据结构考试题库
绪论 一、填空题 1.数据的逻辑结构被分为集合、(线性结构)、(树形结构)和(图状结构)四种。 2.物理结构是数据结构在计算机中的表示，又称为(存储结构)。 3.数据元素的逻辑结构包括( 线性)、(树)和图状结构3种类型，树形结构和图状结构合称为(非线性结构)。 4.(数据元素)是数据的基本单位，(数据项)是数据不可分割的最小单位。 5.线性结构中元素之间存在(一个对一个)关系，树形结构中元素之间存在(一个对多个)关系，图状结构中元素之间存在(多个对多个)关系。 ？6.数据结构是一门研究非数值计算的程序设计问题中：计算机的(数据元素)以及它们之间的(关系)和(运筹)等的学科。 7.算法的五个重要特性为有穷性、确定性、(输入)、(输出)和(可行性)。 二、选择题 1.数据的不可分割的基本单位是(D)。 A.元素 B.结点 C.数据类型 D.数据项 *2.线性表的逻辑顺序与存储顺序总是一致的，这种说法(B)。 A.正确 B.不正确 C.不确定 D.无法选择 3.线性结构是指数据元素之间存在一种(D)。 精心整理，用心做精品2
A.一对多关系 B.多对多关系 C.多对一关系 D.一对一关系 4.在数据结构中，从逻辑上可以把数据结构分成(A)。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 5.线性表若采用链式存储结构时，要求内存中可用存储单元的 地址( D)。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以 三、简答题 1.算法的特性是什么。 答：有穷性确定性可行性有0或多个输入有1或多个输出线性结构 一、填空题 1.在一个长度为n的线性表中删除第i个元素（1≤i≤n）时，需向前移动(n-i)个元素。 2.从循环队列中删除一个元素时，其操作是(先移动队首指针，后取出元素)。 3.在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为(p->next)。 4.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把(p->next)的值赋给q->next，然后(q->date)的值赋给p->next。 5.从一个栈删除元素时，首先取出(栈顶元素)，然后再使(栈顶指针)减1。 6.子串的定位操作通常称做串的(模式匹配)。 精心整理，用心做精品3
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.以顺序方式存储，且数据元素有序
清华园五年级插班生考试卷 一、我会看拼音写词语。（10分） d àng y àng f ēng lu án ji ě sh ì j ù hu ì bi àn l ùn ）（ ）（ ）（ ）（ ） h óng w ěi y óu y ù w ǔ d òng zh ēn ch á c án k ù ）（ ）（ ）（ ）（ ） 二、组词（6分） 幕（ ） 瑕（ ） 陪（ ） 梢（ ） 墓（ ） 假（ ） 培（ ） 悄（ ） 暮（ ） 暇（ ） 倍（ ） 哨（ ） 三、选择正确的解释，把序号放在括号里。（7分） 和 ①性格平和，和缓 ②和谐 ③结束战争或争执 ④下棋不分胜负 1、湖光秋月两厢和 。 （ ） 2、王老师对待同学很温和 。 （ ） 3、真希望和平之花永驻人间 。（ ） 4哎，这盘棋又和了 （ ） 观 ①看 ②竞相或者样子 ③对事物的看法或认识 1、只要留心观察生活，就不愁写文章时“无话可说”。 （ ） 2、自古以来，钱塘江大潮就被称为“天下奇观”。 （ ） 3、在《红岩》中，我被革命先烈的乐观主义精神深深感动。 （ ） 四、按要求写句子（13分） 1、英勇的解放军奋不顾身打退了敌人一次又一次的进攻。（缩写句子） 2、火车驶过田野。（扩写句子） 3、小红一直永远感激着她的启蒙老师。（修改病句） 4、“眼前这些难道还不够吗？”班杰明一边微笑，一边说道。（改成陈述句）
5、小河向前流去。（拟人句） 6、有一天，王明在马路上发现一个学生在草坪里玩耍，他去劝那个学生，那个学生却说：“踩得人多了，少我一个不少，多我一个不多，有什么关系啊？”接下来王明该怎么说？3分 五、阅读短文，回答问题（14分） ＿＿＿＿＿＿＿＿＿＿＿ 春天到了，大地复苏，花儿开放，整个大自然充满了生机，我十分喜爱这生机勃勃的春天，尤其爱春天里那绿油油的小草。 我家门前有一片空地，上面种着小草，它们是那样富有［生机、生命］，春天一到，一下子就铺开了一片绿色的天地。细看，它们是嫩绿色的，水灵灵的，多么喜人！ 一阵风吹过，小草跳起了欢乐的舞蹈，时而舒展双臂，时而左右摇摆。它们像一群活泼的小女孩，天真可爱。这时你如果有空来欣赏一下，一定会叫你心旷神怡，乐而忘返。 你别看小草这样［软弱、柔弱］，可它永远不会向暴风雨低头。有一天，一阵狂风过后，突如其来地下了一场大雨。风雨过后，我赶紧去看那小草。呀！小草好像被折磨得奄奄一息了，有的歪歪斜斜，有的身子贴地。但我相信，它们是不会在暴风雨下屈服的。果然，小草又慢慢挺直了腰，尽管脸上还带着晶莹的泪珠！它们好像在骄傲地说：“你看，我们是多么顽强啊！” 小草，没有鲜花那么娇艳，没有白杨那么［挺拔、挺立］，可是它的生命力是多么［顽强、坚强］！人们说“疾风知劲草”，小草是当之无愧的。 1．给短文加个题目，写在文首的横线上。（2分） 2．用“﹨”划去［］里用得不恰当的词语。（2分） 3．用﹏﹏画出文中的一个比喻句。（2分） 4．下面对于课文内容的表述，（）句话更准确。（填序号）（2分） ①本文表现了作者喜爱春天的思想感情。②本文赞扬了作者喜爱小草的思想感情。 ③本文赞扬了小草坚强不屈，有顽强的生命力。④本文赞扬了小草的美丽可爱。 5．你从文中的小草身上学习到了什么？请你写出几句赞美小草的话。（6分）
数据结构期末考试试题及答案 、选择题 评价一个算法时间性能的主要标准是()。1. A、算法易于调试 B、算法易于理解 C、算法的稳定性和正确性 D、算法的时间复杂度 )等五个特性。计算机算法具备有输入、输出、 2. A、可行性、可移植性和可扩充性 B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 D、XX、稳定性和XX 。带头结点的单链表head为空的判定条件是()3. A、h ead==NULL B、h ead->next==NULL C、head->next==head D、head！=NULL 以下关于线性表的说法不正确的是()。4. A、线性表中的数据元素可以是数字、字符、记录等不同类型。 B、线性表中包含的数据元素个数不是任意的。
C、线性表中的每个结点都有且只有一个直接前趋和直接后继。 D、存在这 样的线性表：表中各结点都没有直接前趋和直接后继。 在顺序表中，只要知道()，就可在相同时间内求出任一结点的存储地址。 5.A、基地址 B、结点大小 C、向量大小 D、基地址和结点大小 ()运算中，使用顺序表比链表好。6. A、插入 B、删除 C、根据序号查找 D、根据元素值查找一个长度为n的顺序表中，向第i个元素之前插入一个新元素时，需要向后移动()个元素7.A、n-i B、n-i+1 C、n-i-1 D、i ()适合作为经常在首尾两端操作线性表的存储结构。8. A、顺序表 B、单链表 C、循环链表 D、双向链表
栈和队列的共同点是() 9. A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 一个队列的入列序列是1234，则队列的输出序列是()。10. A 、4321 B 、12 3 4 C 、1432 D 、 3241队列与一般的线性表的区别在于()。11. A、数据元素的类型不同 B、运算是否受限制 C、数据元素的个数不同 D、逻辑结构不同 假上溢”现象会出现在()中。12. A、循环队列 B、队列 C、链队列 、顺序队列D.二、填空
数据结构试卷（一） 一、选择题（20分） 1．组成数据的基本单位是（ 1.C ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ C ）。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3．数组的逻辑结构不同于下列（D）的逻辑结构。 (A) 线性表(B) 栈(C) 队列(D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（C）个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（.A ）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（.C ）。 (A) 6 (B) 4 (C) 3 (D) 2 7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C ）。 (A) 100 (B) 40 (C) 55 (D) 80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8.B (A) 3 (B) 4 (C) 5 (D) 1 9．根据二叉树的定义可知二叉树共有（B）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法，则（B ）的空间复杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 二、填空题(30分) 1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元 素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。 2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________， 在链式存储结构上实现顺序查找的平均时间复杂度为___________。 3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指 针域，__________个空指针域。 4.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点 B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表 结点。 6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。 7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。 8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编 号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。 9.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i 绪论 一、填空题 1.数据的逻辑结构被分为集合、（线性结构）、（树形结构）和（图状结构）四种。 2. 物理结构是数据结构在计算机中的表示，又称为（存储结构）。 3. 数据元素的逻辑结构包括（线性）、（树）和图状结构3 种类型，树形结构和图状结构合称为（非线性结构）。 4. （数据元素）是数据的基本单位，（数据项）是数据不可分割的最小单位。 5. 线性结构中元素之间存在（一个对一个）关系，树形结构中元素之间存在（一个对多个）关系，图状结构中元素之间存在（多个对多个）关系。 ？ 6.数据结构是一门研究非数值计算的程序设计问题中：计算机的（数据元素）以及它们之间的（关 系）和（运筹）等的学科。 7. 算法的五个重要特性为有穷性、确定性、（输入）、（输出）和（可行性）。 二、选择题 1. 数据的不可分割的基本单位是（D）。 A.元素 B.结点C数据类型D.数据项 *2. 线性表的逻辑顺序与存储顺序总是一致的，这种说法（B）。 A.正确 B.不正确C不确定 D.无法选择 3. 线性结构是指数据元素之间存在一种（D）。 A.一对多关系 B.多对多关系C多对一关系D.—对一关系 4. 在数据结构中，从逻辑上可以把数据结构分成（A）。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C线性结构和非线性结构D.内部结构和外部结构 5. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。 A.必须是连续的 B.部分地址必须是连续的 C. 一定是不连续的 D.连续不连续都可以 三、简答题 1. 算法的特性是什么。 答：有穷性确定性可行性有0 或多个输入有 1 或多个输出 线性结构 一、填空题 1?在一个长度为n的线性表中删除第i个元素（1< i产时，需向前移动（n-i）个元素。 2. 从循环队列中删除一个元素时，其操作是（先移动队首指针，后取出元素）。 3?在线性表的单链接存储中，若一个元素所在结点的地址为p,则其后继结点的地址为（p-> next）。 4. 在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把（p->next）的值赋给q->next，然后（q->date）的值赋给p->next。 5. 从一个栈删除元素时，首先取出（栈顶元素），然后再使（栈顶指针）减1。 6. 子串的定位操作通常称做串的（模式匹配）。 7. 设目标T= ‘ abccdcdccba,模式P= ‘ cdc则第（六）次匹配成功。。 8. 顺序栈S 中，出栈操作时要执行的语句序列中有S->top（--）；进栈操作时要执行的语句序列中有S->top（++）。 六年级插班生考试数学试题 一、 我会填（10分，每空1分） 1、姐弟俩从家走到学校，姐姐用了8分钟，弟弟用了10分钟，姐姐和弟弟的速度比是（ ）。 2.、植树节，我校植树98棵，全部成活，成活率为（ ）。 3、把5米长的铁丝平均分成9段，每段占全长的（ ），每段长（ ）米。 4、小明开学时在教室的座位用（5，6）表示，编位后他分别向自己的右面和后面移动了2个 座位，现在的座位应该用（ ， ）表示。 5、30:40化成最简整数比是（ : ），比值是（ ）。 6、妈妈今年把10000元钱存入银行，定期3年，年利率4.25%,到期妈妈共取回( )元。 7、把任意长的绳子按三角形内角和3:4:5的比围成一个三角形，围成的是（ ）角三角形。 8、想一眼就能够清楚地看出一个家庭的各项开支占总开支的比例，需要制成（ ） 统计图。 二、我会算（能简算的要简算）（10分） 1411×338×167 37.5%×94×1112 121×2.5×96÷4 1 5132531?+÷ 10 7÷［（56 －14 ）×24］ 三、解决问题。（20分） 1、小英看一本120页的故事书，第一天看了全书的5 1，第二天看了全书的25%，两天一共看了多少页？(4分) 2、一列火车的速度是180千米/小时。一辆汽车的速度是这列火车的9 5，是一架喷气式飞机的9 1。这架喷气式飞机的速度是多少？(4分) 3、2000年第五次全国人口普查结果表明，我国人口最多的两个省是河南和山东，山东约有9000万人，约比河南少 46 1。河南大约有多少万人？（列方程解）(4分) 4、校园里有杨树20棵，杉树的棵树是杨树的60%，杉树有多少棵？ 5、用120厘米的铁丝做一个长方体的框架。长、宽、高的比是3:2:1。这个长方体的长、宽、 高分别是多少？（4分） 7th day 插班生基础班板书词条自测I'd like to exchange this dress for one in a smaller size. to exchange honour for wealth the conveyance of goods by rail He is liable to be reached by flattery. to be likely to exact a high price to be apt to commit suicide to be inclined to compromise to be prone to be angry/anger to be required to help with household tasks to be obliged to use stronger measures to be bound to like it to entail a huge political risk The alteration would entail an expenditure of 50 pounds. to necessitate changing our plans legible handwriting/signature an illegible signature/price a reliable method intelligible lecture a negligible difference an eligible candidate a distinct smell of gas 数据结构考试及答案（） 作者: 日期: 2 数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D） A 必须是连续的B部分地址必须是连续的 C 一定是不连续的D可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为 （D ）。 An B n/2 C （n-1）/2 D （n+1）/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（D ）o 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 ）o 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 + n） % 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 (i nt i=0;i 要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题（每小题2分，共20分） 1. 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 。 A. 数据的处理方法 B. 数据元素的类型 C. 数据元素之间的关系 D. 数据的存储方法 2. 下述函数中对应的渐进时间复杂度（n 为问题规模）最小是 。 A.T 1(n)=nlog 2n+5000n B.T 2(n)=n 2-8000n C.T 3(n)= n n 2 log -6000n D.T 4(n)=7000log 2n 3. 设线性表有n 个元素，以下操作中， 在顺序表上实现比在链表上实现效率更高。 A.输出第i （1≤i ≤n ）个元素值 B.交换第1个元素与第2个元素的值 C.顺序输出这n 个元素的值 D.输出与给定值x 相等的元素在线性表中的序号 4. 设n 个元素进栈序列是p 1，p 2，p 3，…，p n ，其输出序列是1，2，3，…，n ，若p 3=3，则p 1的值 。 A.可能是2 B.一定是2 C.不可能是1 D.一定是1 5. 以下各种存储结构中，最适合用作链队的链表是 。 A.带队首指针和队尾指针的循环单链表 B.带队首指针和队尾指针的非循环单链表 C.只带队首指针的非循环单链表 D.只带队首指针的循环单链表 6. 对于链串s （长度为n ，每个结点存储一个字符），查找元素值为ch 的算法的时间复杂度为 。 A.O(1) B.O(n) C.O(n 2) D.以上都不对 7. 设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素a[3][5]的存储地址为1000，则a[0][0]的存储地址是 。 A.872 B.860 C.868 D.864 8. 一个具有1025个结点的二叉树的高h 为 。 A.11 B.10 C.11～1025 D.12～1024 9. 一棵二叉树的后序遍历序列为DABEC ，中序遍历序列为DEBAC ，则先序遍历序列为 。 A.ACBED B.DECAB C.DEABC D.CEDBA 10. 对图1所示的无向图，从顶点1开始进行深度优先遍历；可得到顶点访问序列 。数据结构考试题库
六年级插班生试卷
插班生考试英语复习资料
数据结构考试及答案()
数据结构考试题
相关主题
文本预览