二.阅读理解题
习题：[2-1]分析程序
在下面的每个程序另，线性表La的类型为List,元素类型ElemType为int,假定每个程序是连续执行的，试写出每个程序执行后得到的线性表La。
1.int i;
List La;
InitList(La);
Int a[]={48,26,57,34,62,79};
for (i=0;i<6,i++)
InsertList(La,a[i],1);
TraverseList(La);
2.ClearList(La);
InitList(La);
for (i=0;i<6,i++)
InsertList(La,a[i],0);
TraverseList(La);
3.int x;
InsertList(La,56,0);
DeleteList(La,x,1);
DeleteList(La,x,1);
InsertList(La,x,-1);
TraverseList(La);
4.for(i=1;i<=3;i++)
{ int x=GetList(La,i);
If(x%2==0) DeleteList(La,x,0);
}
TraverseList(La);
5. ClearList(La);
InitList(La);
for(i=0;i<6;i++)
InsertList(La,a[i],-1);
x=a[5];
DeleteList(La,x,0);
SortList(La);
InsertList(La,a[5]/2,0);
TraverseList(La);
ClearList(La);
参考答案:
1.(79,62,34,57,26,48)
2.(26,34,48,57,62,79)
3.(48,56,57,62,79,34)
4.(56,57,79,34)
5.(26,34,39,48,57,62)
习题：[[3-3]分析程序
写出下列每个主程序段的运行输出结果.
1.void main()
{ set a ;
InitSet (a) ;
ElemType r[8]={1,5,90,5,7,25,34,16} ;
Int i
for{i=0 ;i<8 ;i++} Insertset (a, r[i]) ;
ElemType x=25 , y=90 ;
Deleteset ( a,x) ;
Deleteset ( a,y) ;
Outputset(a) ;
Cout< } 2.void main( ) { ElemType r[8]={1,5,90,5,7,25,34,16} ; set a ; Initset(a) ; set b ; Initset(b) ; set c; Initset(c) ; int i for (i=0;i<8;i++) Insertset(a ,r[i] ) ; for (i=0;i<8;i++) Insertset(b ,r[i] ) ; Unionset( a,b,c) ; Outputset( c) ; Interseset (a,b,c) ; Outputset ( c) ; Diffdrenceset(a,b,c) ; Outputset ( c) ; Clearset(a) ; Clearset(b) ; Clearset(c) ; } 3.void main( ) { ElemType r[8]={1,5,90,5,7,25,34,16} ; SNode * a ; Initset (a) ; int i for ( i=0;i<8 ;i++) Insertset(a ,r[i] ) ; Outputset (a) ; ElemType x=34 ; Deleteset ( a , x) ; Interseset (a , 48) ; x=5 ; Deleteset ( a , x) ; Outputset (a) ; Clearset ( a) ; } 4.void main( ) { SNode * a ; Initset (a) ; SNode * b ; Initset (b) ; SNode * c; Initset c) int i ElemType r[8]={1,5,90,5,7,25,34,16} ; ElemType r1[5]=(5,60 ,16,30,8) ; for ( i=0;i<8 ;i++) Insertset(a ,r[i] ) ; for ( i=0;i<8 ;i++) Insertset(b ,r[i] ) ; Unionset( a,b,c) ; Outputset( c) ; Interseset (a,b,c) ; Outputset ( c) ; } 参考答案: 1. 1 5 34 7 16 0 5 2. 1 5 90 7 25 34 16 60 30 8 5 1 6 34 1 90 7 25 3. 16 34 25 7 90 5 1 48 16 25 7 90 1 4. 60 30 8 1 5 90 7 25 34 16 5 16 习题：[4-2]分析程序 算法分析题,写出每个算法的功能 1.int AE(int a[],int n) { if(n==0) return 0; else return a[n-1]+AE(a,n-1); } 2.int AF(int k, int s) //第1次使用AF(0,0)调用此算法{ if(s>=1000) return k-1; else { k++; s+=k*k; return AF(k,s); } } 3.void Transform(long num) //num为正整数 { Stack a; InitSTack(a); while(num!=0) { int k=num % 16; Push(a,k); num/=16; } while(!EmptyStack(a)) { int x=Pop(a); if(x<10) cout< else { swich(x){ case 10: cout<<'A';break; case 11: cout<<'B';break; case 10: cout<<'C';break; case 10: cout<<'D';break; case 10: cout<<'E';break; case 10: cout<<'F'; } } } cout< } 4.void Fun1(Stack& s1, int n) { srand(time(0)); //srand()函数stdlib.h头文件中定义int i=0,j; //time函数在tiime.h头文件中定义 while(i int x=rand() % 100; //rand函数在stdlib.h头文件中定义 int y=int(sqrt(x)); //平方根函数sqrt在math.h头文件中定义for(j=2;j<=y;j++) if(x%j==0) break; if(j>y && x>10) {i++;Push(s1,x);} } } 5.void Fun2(Queue& q1, Queue& q2, int n) { int i,x; cout<<"从键盘输入"< for(i=0; i cin>>x; if(x%2) EnQueue(q1,x); else EnQueue(q2,x); } } 参考答案: 1.求数组A中N个元素之和. 2.计算出满足12+22+…+n2 => 32+…+n2 < 1000 不等式的最大值n值. 3.把一个正整数num转换为一个十六进制数输出. 4.向顺序栈s1中插入n个11—99之间的随机数. 5.把由键盘上输入的n个整数,按奇数和偶数分别插入顺序队列q1和q2中. 习题：[5-2]分析程序 算法分析题 1.下面函数的功能是返回二叉树BT中值为X的结点所在的层号，请在划有横线的地方填写核实内容。 int NodeLevel(BTreeNode*BT, ElemType X) { if(BT==NULL) return 0; //空树的层号为0 else if(BT->data==X) return 1; //根结点的层号为1 else { //向子树中查找X结点 int c1=NodeLevel(BT->left,X); if(c1>=1)______(1)________; int c2=_______(2)________; if________(3)_________; //若树中不存在X结点则返回0 return 0； } } 2.指出下面函数的功能。 BTreeNode* BTreeSwopX(BTreeNode* BT) { if(BT==NULL) return NULL; else { BTreeNode* pt=new BTreeNode; pt->data=BT->data; pt->right=BTreeSwopX(BT->left); pt->left=BTreeSwopX(BT->right); return pt; } } 3.已知二叉树种的结点类型STreeNode定义如下。 struct STreeNode {datatype data; STreeNode*lchild,*rchild,*parent;}; 其中，data为结点值域，lchild和rchild分别为指向左、右孩子结点的指针域，parent为指向父亲结点的指针域。根据下面函数的定义指出函数的功能。算法中参数ST指向一棵二叉树，X保存一个结点的值。 STreeNode*PN(STreeNode*ST, DataType& X) { if(ST==NULL) return NULL; else { StreeNode*mt; if(ST->data==X) return ST->parent; else if(mt=PN(ST->lchild,X)) return mt; else if(mt=PN(ST->rchild,X)) return mt; return NULL; } } 4.指出下面函数的功能. void BTC (BTreeNode * BT ) { if (BT!=NUL) { if(BT->left!=NULL && BT->right !=NULL) if (BT->left->data>BT->right->data) { BTreeNode * t=BT->left ; BT->left=BT->right ; BT->right=t ; } BTC(BT->left) ; BTC(BT->right ) ; } } 5.设BT指向一棵二叉树,该二叉树的广义表表示为a( b(a , d(f) ) ,c( e(,a (k) ), b)) ,则依次使用 BTC1( BT'a' C)、BTC1( BT'b’ C)、BTC1( BT'c' C) 、BTC1( BT'g' C) 调用下面算法时，假定每次调用时C的初始值均为0 ，引用变量的带回值依次为 ----（1）---- 、----（2）---- 、----（3） ----- 和-----（4）-----。void BTC1(BTreeNode * BT ,char x ,int & k ) { if (BT!=NULL ){ if{BT->data==x) k++ ; BTC1( BT->left, x,k ) ; BTC1( BT->right, x,k ) ; } } 6.下面的函数的功能是从二叉树BT中查找值为x 的结点，若查找成功则返回结点地址，否则返回为空。请在划有横线的地方填写合适内容。 BTreeNode * BTF (BTreeNode * BT ,ElemType x) { if(BT ==NULL) _____(1)____ ; else { if(BT->data==x) _____(2)____ ; else { BTreeNode * t ; if(t=BTF(BT->left,x)) _____(3)__; ________(4)_________; else return NULL ; } } } 7．指出下面函数的功能。 void preserve ( BTreeNode * BT ,ElemType a[] ,int n) { static int i=0 ; if (BT!=NULL) { preserve(BT->left ,a ,n) a[i++]=BT->data ; preserve( BT->right ,a ,n) ; } } 参考答案: 1.(1) return c1+1 (2) NodeLevel(BT->right,X) (3) （c2>=1）return c2+1. 2. 生成一棵新二叉树并返回树根指针, 该二叉树是已知二叉树BT中所有的左右子树交换的结果. 3. 从树根指针为ST的二叉树中查找值为X的结点,返回指向父结点的指针. 4. 当BT中每个结点的左孩子的值>右孩子的值时交换左右子树. 5. (1)3 (2)2 (3)1 (4)0 6. (1)return NULL (2)return BT (3)return t (4)if(t=BTF(BT->right,x))return t 7. 对具有n个结点的二叉树进行中序遍历,把得到的结点值序列保存到数组a 中. EBR，叫做扩展MBR（Extended MBR），位于硬盘的某柱面0磁道1扇区 1.簇（cluster） 是DOS给文件系统分配磁盘空间的最小单位。由若干连续的逻辑扇区组成，不同的盘，簇的大小不同，簇是从2开始编号，见表6-1。 逻辑扇区号=（簇号-2）×扇区数/簇+数据区首扇区号 2.BOOT记录： 第一部分：0～2字节为跳转指令，转向启动码区。 第二部分：3～10字节为厂商标识字段，如MSDOS5.0。 第三部分：11～61字节为磁盘参数表（51字节）。 第四部分：62～509字节为启动程序（438字节）。 最后：55,AA字节。 51字节BPB表（BIOS Parameter Block） OB－OC：每扇区字节数(512) OD：扇区数/簇 0E－0F：保留扇区（指Boot区） 10：FAT个数 11－12：根目录最大登记项数 13－14：本分区扇区总数（小于32M的分区，大于32MB时,为0） 15：介质描述符 16－17：每个FAT扇区数 18－19：每道扇区数 1A－1B：磁头数 1C－1F：本分区前的扇区数（隐含扇区，即从0（X）柱0头1扇到0（X）柱1头1扇之间的扇区，由于不能为DOS访问，故称为隐含扇区）。 20－23：大容量盘总扇区数。 24：BIOS设备号（hex：HD=8x） 25：未使用 26：扩展引导标记（29H） 27-2A：卷序列号（随机） 2B-35：卷标，分区标识，如：WIN98 36-3D：文件系统格式（FAT16） 3.FAT（文件配置表） FAT有两个，当第一个损坏时，为人工修复提供方便，DOS不会自动用第二个去修复第一个FAT，而DOS实际上没有用尽2个FAT占用的扇区，因为可作为他用。FAT登记盘上簇的使用情况，登记项有12位、16位和32位之分，下面以16位为例说明FAT的格式。 16位FAT格式： 簇号（表项） 0000H 0001H 0002H … NNNNH 类型保留簇使用簇 含义介质标志记录文件簇号链 数据结构 一、单选题 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） 数据结构例题（及答案） 项目一习题(答案) 一选择题 1. 算法的计算量的大小称为计算的(B )。 A( 效率 B. 复杂性 C. 现实性 D. 难度 2.算法的时间复杂度取决于(C ) A(问题的规模 B. 待处理数据的初态 C. A和B 3(从逻辑上可以把数据结构分为(C )两大类。 A(动态结构、静态结构 B(顺序结构、链式结构 C(线性结构、非线性结构 D(初等结构、构造型结构 4(连续存储设计时，存储单元的地址(A )。 A(一定连续 B(一定不连续 C(不一定连续 D(部分连续，部分不连续 5. 以下属于逻辑结构的是(C )。 A(顺序表 B. 哈希表 C.有序表 D. 单链表 二、判断题 1. 数据元素是数据的最小单位。(×) 2. 记录是数据处理的最小单位。(×) 3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系;(×) 4(程序一定是算法。(×) 5. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×) 6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×) 7. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。(?) 8. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. (×) 三、填空 1(数据的物理结构包括数据元素的表示和数据元素间关系的表示。 2. 对于给定的n个元素,可以构造出的逻辑结构有集合，线性结构，树形 结构，图状结构或网状结构四种。 3(数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而 逻辑关系是指数据元素之间的关联方式或称“邻接关系”。 4(一个数据结构在计算机中表示(又称映像) 称为存储结构。 5(抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内部如何表 示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响 其外部使用。 6(数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。 7. 数据结构是研讨数据的逻辑结构和物理结构，以及它们之间的相互 关系，并对与这种结构定义相应的操作(运算)，设计出相应的算法。 ( 一个算法具有5个特性: 有穷性、确定性、可行性，有零个或多个输入、 有一个或多个输8 出。 四、应用题 1. 1. 数据结构是一门研究什么内容的学科, 答:数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象 及对象间的关系和施加于对象的操作等的学科 2. 2. 数据元素之间的关系在计算机中有几种表示方法,各有什么特点, 答:四 种表示方法 数据结构试卷（五） 一、选择题(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.在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。 栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 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.以顺序方式存储，且数据元素有序 一、选择题(20分) 1．下面关于线性表的叙述错误的是（D ）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 2．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A ）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 3．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C ）。 (A) 9 (B) 10 (C) 11 (D) 12 4．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（B ）。 (A) O(1) (B) O(log2n) (C) (D) O(n2) 5．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（B ）方法可以达到此目的。 (A) 快速排序(B) 堆排序(C) 归并排序(D) 插入排序 第9小题分析：9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为O(log2n)。 6.下列四种排序中（D ）的空间复杂度最大。 (A) 插入排序(B) 冒泡排序(C) 堆排序(D) 归并排序 7．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C ）。 (A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2) 8．设一棵二叉树的深度为k，则该二叉树中最多有（D ）个结点。 (A) 2k-1 (B) 2k(C) 2k-1(D) 2k-1 9．在二叉排序树中插入一个结点的时间复杂度为（B ）。 (A) O(1) (B) O(n) (C) O(log2n) (D) O(n2) 10．设用链表作为栈的存储结构则退栈操作（B ）。 (A) 必须判别栈是否为满(B) 必须判别栈是否为空 (C) 判别栈元素的类型(D) 对栈不作任何判别 11．下列四种排序中（A ）的空间复杂度最大。 (A) 快速排序(B) 冒泡排序(C) 希尔排序(D) 堆 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.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不 超过（A ）。 (A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1) 14．数据的最小单位是（A ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 15．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（D ）。 (A) O(log2n) (B) O(1) (C) O(n2) (D) O(n) 空间数据结构 摘要：空间数据模型和空间数据结构是地理信息系统（GIS）课题的中心内容。本文对空间数据结构的定义、分类进行了一定的研究性的归纳与总结。 关键词：空间数据结构，矢量数据，栅格数据 引言 GIS中空间数据结构和空间数据模型是紧密相关的。数据模型的建立必须通过一定的数据结构，但两者之间也有非常大的区别。数据模型是一个总得概念，是人为概念化的真实，是对现实世界的提取，对现实世界的认识和选择。而数据结构指数据元素之间的相互关系，它是软件常规内涵，根据空间数据结构和数据模型的特点及其关系，可以建立空间数据库系统。 空间数据结构定义 空间数据结构是带有空间数据单元的集合。这些数据单元是数据的基本单 位，一个数据单元可以有几个数据项组成，数据单元之间存在某种联系叫做结构。 所以，研究空间数据结构，是指空间目标间的相互关系，包括几何和非几何的关 系，数据结构是数据模型的表述，数据结构往往通过一系列的图表和矩阵，以及 计算机码的数据记录来说明。 空间数据结构的分类 矢量数据结构 定义 矢量数据结构是基于矢量模型，利用欧几里得(EUCLID)几何学中的点、线、 面及其组合体来表示地理实体的空间分布，是通过记录坐标的方式，尽可能精确 地表示点线多边形等地理实体，自然地理实体的位置是用其在坐标参考系中的空 间位置来定义的，坐标空间设为连续，允许任意位置长度和面积的精确定义，其 特点是定位明显，属性隐含。 GIS采用的矢量数据结构模型，是将空间地质实体抽象成点、线、面三种几 何要素，矢量数据结构通过优化拓扑结构表达空间实体的相关关系，为空间数据 库建立基本框架。 矢量数据结构的特点 优点：数据按照点、线或多边形为单元进行组织，结构简单、直观、易实现 以实体为单位的运算和显示。 缺点： 数据结构试卷（一） 一、选择题（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.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (count 绪论 一、填空题 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（++）。 基本概念典型例题 一、单项选择题 [例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是( ①)的有穷集合，R是D上( ②)的有限集合。 ①A.算法B. 数据元素C. 数据操作D. 逻辑结构 ②A. 操作B. 映像C. 存储D．关系 解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。 [例6-2]数据的常用存储结构中不包括( )。 A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。 [例6-3] 算法指的是( ①)，它必须具备( ②)这三个特性。 ①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法 ②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性 解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它 必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本 题答案为：①㈠②B。 [例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(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开始进行深度优先遍历；可得到顶点访问序列 。 1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998 三、1 （5分）】 LinkedList Union(LinkedList la,lb) { pa=la->next; pb=lb->next; la->next=null; while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data) { r=pa->next; pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=r; } else {r=pb->next; pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=r; } while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null) {r=pb->next; pb->next=la->next; la->next=pb; pb=r; } } 1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】 LinkedList Union(LinkedList ha, hb)∥ha和hb是两个无头结点的数据域值递增有序的单链 ｛LinkedList 表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表。 la; la=(LinkedList)malloc(sizeof(LNode)); la->next=ha; pa=ha; pb=hb; pre=la; while(pa&&pb) if(pa->data 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。【中山大学1998 二、1（2分）】 A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B. 为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学1996 一、4（2分）】 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001 一、2（2分）】 A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学2001 一、10（3分）】 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ （组织设计）硬盘数据组织 结构 EBR，叫做扩展MBR（ExtendedMBR），位于硬盘的某柱面0磁道1扇区 1.簇（cluster） 是DOS给文件系统分配磁盘空间的最小单位。由若干连续的逻辑扇区组成，不同的盘，簇的大小不同，簇是从2开始编号，见表6-1。 逻辑扇区号=（簇号-2）×扇区数/簇+数据区首扇区号 2.BOOT记录： 第壹部分：0～2字节为跳转指令，转向启动码区。 第二部分：3～10字节为厂商标识字段，如MSDOS5.0。 第三部分：11～61字节为磁盘参数表（51字节）。 第四部分：62～509字节为启动程序（438字节）。 最后：55,AA字节。 51字节BPB表（BIOSParameterBlock） OB－OC：每扇区字节数(512) OD：扇区数/簇 0E－0F：保留扇区（指Boot区） 10：FAT个数 11－12：根目录最大登记项数 13－14：本分区扇区总数（小于32M的分区，大于32MB时,为0） 15：介质描述符 16－17：每个FAT扇区数 18－19：每道扇区数 1A－1B：磁头数 1C－1F：本分区前的扇区数（隐含扇区，即从0（X）柱0头1扇到0（X）柱1头1扇之间的扇区，由于不能为DOS访问，故称为隐含扇区）。 20－23：大容量盘总扇区数。 24：BIOS设备号（hex：HD=8x） 25：未使用 26：扩展引导标记（29H） 27-2A：卷序列号（随机） 2B-35：卷标，分区标识，如：WIN98 36-3D：文件系统格式（FAT16） 3.FAT（文件配置表） FAT有俩个，当第壹个损坏时，为人工修复提供方便，DOS不会自动用第二个去修复第壹个FAT，而DOS实际上没有用尽2个FAT占用的扇区，因为可作为他用。FAT登记盘上簇的使用情况，登记项有12位、16位和32位之分，下面以16位为例说明FAT的格式。 16位FAT格式： 簇号（表项）0000H0001H0002H…NNNNH 类型保留簇使用簇 含义介质标志记录文件簇号链 保留簇的第壹字节为磁盘介质标志，后为填充位，全为FFH。使用簇能够是； 0000:自由 FFF6:备用 FFF7:坏簇 FFF8-FFFF:文件结束 其它：文件的下壹簇 4.文件目录表（根目录表FDT） 记录文件名、属性、建立时间、日期、首簇及长度的壹个表。每个文件占用表32字节， O0-O7：文件主名（文件被删除后，00字节为E5H） O8-0A：文件扩展名 0B：文件属性 27H： ↑↑↑↑↑↑ X:未用，填0档案子目录卷标系统隐含只读 0C-15：保留（全0） 16-17：建立文件的时间 18-19：建立文件的日期 1A-1B：文件首簇 1C-1F：文件长度 LFNentry:长文件名项，属性字节为0F表示LFNentry Cr.timerefinementin10msunits:以10ms为计时精度 5.主引导记录（MBR）硬盘数据组织结构
数据结构考试试题及答案
数据结构经典例题
数据结构试卷(五)及答案
经典数据结构面试题(含答案)
《数据结构》期末考试题及答案
大数据结构经典复习题(仅供参考)
空间数据结构
数据结构试卷带答案
数据结构经典例题
数据结构考试题库
数据结构典型例题
数据结构考试题
数据结构经典算法试题
数据结构考试题库含参考答案
数据结构课后习题详解(超完整,超经典)
{组织设计}硬盘数据组织结构
相关主题
文本预览