数据结构上机例题及答案

习题二

⒉１描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点）。解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。

2.2简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。

解：顺序存储是按索引直接存储数据元素，方便灵活，效率高，但插入、删除操作将引起元素移动，降低了效率；而链式存储的元素存储采用动态分配，利用率高，但须增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入和删除十分简单。顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况；而链式存储适用于频繁进行元素动态插入或删除操作的场合。

2.3 在头结点为h的单链表中，把值为b的结点s插入到值为a的结点之前，若不存在a，就把结点s插入到表尾。

Void insert(Lnode *h,int a,int b)

{Lnode *p,*q,*s;

s=(Lnode*)malloc(sizeof(Lnode));

s->data=b;

p=h->next;

while(p->data!=a&&p->next!=NULL)

{q=p;

p=p->next;

}

if (p->data==a)

{q->next=s;

s->next=p;}

else

{p->next=s;

s->next=NULL;

}

}

2.4 设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B，使A中含有原链表中序号为奇数的元素，而B中含有原链表中序号为偶数的元素，并且保持元素原有的相对顺序。

Lnode *cf(Lnode *ha)

{Lnode *p,*q,*s,*hb;

int t;

p=ha->next;

q=ha;

t=0;

hb=(Lnode*)malloc(sizeof(Lnode));

s=hb;

while(p->next!=NULL)

{if (t==0)

{q=p;p=p->next;t=1;}

else

{q->next=p->next;

p->next=s->next; s->next=p; s=p;

p=p->next; t=0;

}

}

s->next=NULL;

return (hb);

}

2.5设线性表中的数据元素是按值非递减有序排列的，试以不同的存储结构，编写一算法，

将x插入到线性表的适当位置上，以保持线性表的有序性。

⑴顺序表；

解：本题的算法思想是：先找到适当的位置，然后后移元素空出一个位置，再将 x 插入，并返回向量的新长度。实现本题功能的函数如下：

int insert(vector A，int n，ElemType x) /*向量 A 的长度为 n*/

{ int i，j；

if (x>=A[n-1]) A[n]=x /*若 x 大于最后的元素，则将其插入到最后*/ else

{ i=0；

while (x>=A[i]) i++； /*查找插入位置 i*/

for (j=n-1；j>=i；j--) A[j+1]=A[j]； /*移出插入 x 的位置*/

A[i]=x；

n++； /*将 x 插入，向量长度增 1*/

}

return n;

}

⑵单链表。

解：本题算法的思想是先建立一个待插入的结点，然后依次与链表中的各结点的数据域

比较大小，找到插入该结点的位置，最后插入该结点。实现本题功能的函数如下：

node *insertorder(head，x)

node *head; ElemType x;

{

node *s，*p，*q;

s=(node *)malloc(sizeof(node)); /*建立一个待插入的结点*/

s->data=x;

s->next=NULL;

if (head==NULL || xdata) /*若单链表为空或 x 小于第一个结点的

date 域*/

{

s->next=head; /*则把 s 结点插入到表头后面*/

head=s;

}

else

{ q=head; /*为 s 结点寻找插入位置，p 指向待比较的结点，q 指向 p 的

前驱结点*/

p=q->next;

while (p!=NULL && x>p->data) /*若 x 小于 p 所指结点的 data 域值

*/

if (x>p->data) /*则退出 while 循环*/ {

q=p;

p=p->next;

}

s->next=p; /*将 s 结点插入到 q 和 p 之间*/

q->next=s;

}

return(head);

}

2.6假设有A和B分别表示两个递增有序排列的线性表集合（即同一表中元素值各不相同），求A和B的交集C，表C中也依值递增有序排列。试以不同的存储结构编写求得C的算法。

⑴顺序表；

void SqList_Intersect_True(SqList &A,SqList B)//求元素递增排列的线性表A和B的元素的交集并存回A中

{

i=1;j=1;k=0;

while(A.elem[i]&&B.elem[j])

{

if(A.elem[i]

else if(A.elem[i]>B.elem[j]) j++;

else if(A.elem[i]!=A.elem[k])

{

A.elem[++k]=A.elem[i]; //当发现了一个在A,B中都存在的元素

i++;j++; //且C中没有,就添加到C中

}

}//while

while(A.elem[k]) A.elem[k++]=0;

}//SqList_Intersect_True

⑵单链表。

单链表

chnode *or(chnode *head1,chnode *head2)

{ chnode *p1,*p2,*q2,*h,*p;

h=p=malloc(sizeof(chnode));

p->next=NULL;

p1=head1->next;

while(p1)

{ p2=head2;

q2=p2->next;

while((q2->data!=p1->data)&&q2)

{ p2=q2;

q2=q2->next;

}

if(p1->data==q2->data)

p2->next=q2->next;

if(q2)

{ while(p->next)

p=p->next;

p->next=q2;

p=q2;

q2->next=NULL;

}

p1=p1->next;

}

return(h);

}

2.7设计一个算法求两个递增有序排列的线性表A和B 的差集。（每个单链表中不存在重复的元素）

提示：即在A中而不在B中的结点的集合。

typedef int elemtype；

typedef struct linknode

{

elemtype data；

struct linknode *next；

} nodetype；

nodetype *subs(nodetype *heada, nodetype *headb)

{

nodetype *p, *q, *r, *s；

s=(nodetype *)malloc(sizeof(nodetype))；

s->next=heada；

heada=s；

p=heada->next；

r=heada；r->next=NULL；

while (p!=NULL)

{

q=headb；

while (q!=NULL && q->data!=p->data) q=q->next；

if (q!=NULL)

{

s=p->next；

free(p)；p=s；

}

else

{

r->next=p；s=p->next；

r=p；r->next=NULL；

p=s；

}

}

s=heada；heada=heada->next；free(s)；

return heada；

}

2.8设有线性表A=(a1 ,a2 ,...,a m )，B=(b1 ,b2 ,...,b n )。试写一合并A、B为线性表C的算法，使得

(a1 ,b1 ,...,a m ,b m ,b m+1 ,...,b n ) 当m≤n时

C＝｛

(a1 ,b1 ,...,a n ,b n ,a n+1 ,...,a m ) 当m＞n时

A、B和C均以单链表作存储结构，且C表利用A和B中结点空间。

解：假设 A，B 和 C 链表分别具有头结点的指针 a，b 和 c。实现本题功能的函数如下：

node *link(a，b)

node *a，*b;

{

node *r，*s，*p，*q，*c;

c=(node *)malloc(sizeof(node)); /*建立一个头结点*/

r=c;p=a;q=b;

while (p!=NULL || q!=NULL)

{

if (p!=NULL) /*如果 A 链表还存在可取的结点，则复制一个同样的结点链接到 C 中*/

{

s=(node *)malloc(sizeof(node));

s->data=p->data;

r->next=s;

r=s;

p=p->next;

}

if (q!=NULL) /*如果 B 链表还存在可取的结点，则复制一个同样的结点链接到 C 中*/

{

s=(node *)malloc(sizeof(node));

s->data=q->data;

r->next=s;

r=s;

q=q->next;

}

}

r->next=NULL;

s=c;

c=c->next; /*删除头结点*/

free(s);

return(c);

}

2.9试用两种线性表的存储结构来解决约瑟夫问题。设有n个人围坐在圆桌周围，现从第s 个人开始报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m个人又出列，…，如此重复直到所有的人全部出列为止。例如当n=8,m=4,s=1,得到的新序列为：4，8，5，2，1，3，7，6。写出相应的求解算法。

解：

先构造一个循环链表

nodetype *crea(int n)

{ nodetype *s,*r,*h;

int I;

for (i=1;i<=n;i++)

{ s=(nodetype *)malloc(sizeof (nodetype));

s->data=I;s->next=NULL;

if(i==1) h=s;

else r->next=s;

r=s;

}

r->next=h;

return h;

}

void jese (nodetype *h,int m)

{ nodetype *p=h,*q;

int I;

while (p->next!=p)

{for (i=1;i

p=p->next;

if (p->next!=p)

{ q=p->next;

printf(“%d”,q->data);

p->next=q->next;

free(q);

}

p=p->next;

}

printf(“%d”,p->data);

}

2.10已知单链表中的数据元素含有三类字符（即：字母字符、数字字符和其它字符），试编

写算法构造三个环形链表，使每个环形链表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。

解：void split (nodetype *ha,nodetype *hb,nodetype *hc)

{ char c;

nodetype *ra,*rb,*rc,*p=ha->next;

ra=ha;ra->next=NULL;

rb=hb;rb->next=NULL;

rc=hc;rc->next=NULL;

while (p!=ha)

{ c=p->data;

if ((c>=’a’&&c<=’z’)||(c>=’A’&&c<=’Z’))

{ra->next=p;ra=p; }

else if(c>=’0’&&c<=’9’)

{rb->next=p;rb=p;}

else

{rc->next=p;rc=p;}

p=p->next;

}

ra->next=ha;rb->next=hb;rc->next=hc;

}

2.11假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知p为指向链表中某结点的指针，试编写算法在链表中删除结点p 的前趋结点。

解：nodetype *delprev(nodetype *p)

{ nodetype *r=p,*q=r->next;

while (q->next!=p)

{r=r->next;q=r->next;}

r->next=p;

free(q);

return(p);

}

2.12假设有一个单向循环链表，其结点含三个域：pre 、data 和next ， 每个结点的pre 值为空指针，试编写算法将此链表改为双向环形链表。

分析：在遍历单链表时，可以利用指针记录当前访问结点和其前驱结点。知道了当前访问结点的前驱结点位置，就可以给当前访问结点的前驱指针赋值。这样在遍历了整个链表后，所有结点的前驱指针均得到赋值。

Typedef struct lnode

{elemtype data;

struct lnode pre,next;

}lnode,*linklist;

void singletodouble(linklist h)

{linklist pre,p;

p=h->next;

pre=h;

while(p!=h)

{p->pre=pre;

pre=p;

p=p->next;

}

p->pre=pre;

}

2.13设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676

（10），每个元素占一个地址空间，求A[3][3]（10）存放在什么位置？

分析 根据二维数组的地址计算公式：LOC(i,j)=LOC(0,0 )+[n*i+j]*s ，首先要求出数组第二维的长度，即n 值。

解 因为LOC(2，2)=LOC(0,0 )+ 2*n+2=644+2*n+2=676

所以n=（676-2-644）/2=15

LOC(3,3)=LOC(0,0)+3*15+3=644+45+3=692

2.14 设稀疏矩阵采用十字链表结构表示。试写出实现两个稀疏矩阵相加的算法。

解：依题意，C=A+B，则 C 中的非零元素cij只可能有 3 种情况：或者是aij+bij，或者是aij(bij=0)或者是bij(aij=0)。因此，当 B 加到A上时，对A矩阵的十字链表来说，或者是改变结点的val 域值(a+b≠0)，或者不变(b=0)，或者插入一个新结点(a=0)，还可能是删除一个结点(aij+bij=0)。整个运算可从矩阵的第一行起逐行进行。对每一行都从行表头出发分别找到A和 B 在该行中的第一个非零元素结点后开始比较，然后按 4 种不同情况分别处理（假设pa 和pb 分别指向A和 B 的十字链表中行值相同的两个结点）：若pa->col=pb->col且pa->val+pb->val≠0，则只要将aij+bij的值送到pa 所指结点的值域中即可。

（2）若pa->col=pb->col 且pa->val+pb->val=0，则需要在A矩阵的十字链表中删除pa 所指结点，此时需改变同一行中前一结点的right 域值，以及同一列中前一结点的down域值。

（3）若pa->colcol 且pa->col≠0（即不是表头结点），则只需要将pa 指针往右推进一步，并重新加以比较。

（4）若pa->col>pb->col 或pa->col=0，则需要在A矩阵的十字链表中插入一个值为bij 的结点。

实现本题功能的程序如下：

#include

#define MAX 100

struct matnode *createmat(struct matnode *h[])

/*h 是建立的十字链表各行首指针的数组*/

{ int m，n，t，s，i，r，c，v;

struct matnode *p，*q;

printf("行数m，列数n，非零元个数t:");

scanf("%d，%d，%d"，&m，&n，&t);

p=(struct matnode *)malloc(sizeof(struct matnode));

h[0]=p;

p->row=m;

p->col=n;

s=m>n ? m:n; /*s 为m、n 中的较大者*/

for (i=1;i<=s;i++)

{

p=(struct matnode *)malloc(sizeof(struct matnode));

h[i]=p;

h[i-1]->tag.next=p;

p->row=p->col=0;

p->down=p->right=p;

}

h[s]->tag.next=h[0];

for (i=1;i<=t;i++)

{

printf("\t 第%d 个元素(行号r，列号c，值v):"，i);

scanf("%d，%d，%d"，&r，&c，&v);

p=(struct matnode *)malloc(sizeof(struct matnode));

p->row=r;

p->col=c;

p->tag.val=v;

q=h[r];

while (q->right!=h[r] && q->right->col

q=q->right;

p->right=q->right;

q->right=p;

q=h[c];

while(q->down!=h[c] && q->down->row

q=q->down;

p->down=q->down;

q->down=p;

}

return(h[0]);

}

void prmat(struct matnode *hm)

{

struct matnode *p，*q;

printf("\n 按行表输出矩阵元素:\n");

printf("row=%d col=%d\n"，hm->row，hm->col);

p=hm->tag.next;

while (p!=hm)

{

q=p->right;

while (p!=q)

{

printf("\t%d，%d，%d\n"，q->row，q->col，q->tag.val);

q=q->right;

}

p=p->tag.next;

}

}

struct matnode *colpred(i，j，h)

/*根据i(行号)和j(列号)找出矩阵第i 行第j 列的非零元素在十字链表中的前驱结点*/

int i，j; struct matnode *h[];

{

struct matnode *d;

d=h[j];

while (d->down->col!=0 && d->down->row

d=d->down;

return(d);

}

struct matnode *addmat(ha，hb，h)

struct matnode *ha，*hb，*h[];

{

struct matnode *p，*q，*ca，*cb，*pa，*pb，*qa;

if (ha->row!=hb->row || ha->col!=hb->col)

{

printf("两个矩阵不是同类型的，不能相加\n");

exit(0);

}

else

{

ca=ha->tag.next;

cb=hb->tag.next;

do

{

pa=ca->right;

pb=cb->right;

qa=ca;

while (pb->col!=0)

if (pa->colcol && pa->col!=0)

{

qa=pa;

pa=pa->right;

}

else if (pa->col>pb->col || pa->col==0)

{

p=(struct matnode *)malloc(sizeof(struct matnode));

*p=*pb;

p->right=pa;

qa->right=p;

qa=p;

q=colpred(p->row，

p->col，h);

p->down=q->down;

q->down=p;

pb=pb->right;

}

else

{

pa->tag.val+=pb->tag.val;

if (pa->tag.val==0)

{

qa->right=pa->right;

q=colpred(pa->row，

pa->col，h);

q->down=pa->down;

free(pa);

}

else qa=pa;

pa=pa->right;

pb=pb->right;

}

ca=ca->tag.next;

cb=cb->tag.next;

} while (ca->row==0);

}

return(h[0]);

}

main()

{

struct matnode *hm，*hm1，*hm2;

struct matnode *h[MAX]，*h1[MAX];

printf("第一个矩阵:\n");

hm1=createmat(h);

printf("第二个矩阵:\n");

hm2=createmat(h1);

hm=addmat(hm1，hm2，h);

prmat(hm);

}

第二章上机内容

1.设计一个程序，生成两个按值非递减有序排列的线性表LA和LB，再将LA和LB归并为一个新的线性表LC，且LC中的数据仍按值非递减有序排列，输出线性表LA，LB，LC。解：

#include “stdio.h”

#include “alloc.h”

typedef struct node

{

char data；

struct node *next；

} listnode；

typedef struct node *link；

void print(link head)

{

struct node *p；

printf（“\n”）；

printf（“\n”）；

p= head->next；

while(p)

{printf（“%c”, p->data)；p = p->next；}

}

link creat() /*头插法建立单链表*/ {

link head ,s；

char ch；

head = malloc(sizeof(listnode))；

head->next =NULL；

while(( ch= getchar())!=’\n’)

{

s= malloc(sizeof(listnode))；

s->data= ch；

s->next = head->next；

head->next = s；

}

return head；

}

link merge(link a , link b)

{

link p , q , s , c；

c= malloc(sizeof(listnode))；

c->next =NULL；

p=a；

q=b；

while(p->next&&q->next)

{

if (p->next->datanext->data)

{ s = p->next；p->next=s->next；} else

{ s = q->next；q->next = s->next；} s->next = c->next；

c->next = s；

}

while (p->next)

{

s = p->next；

p->next = s->next；

s->next = c->next；

c->next = s；

}

while(q->next)

{

s = q->next；

q->next = s->next；

s->next = c->next；

c->next = s；

}

free(p)；free(q)；

return c；

}

main()

{

link a , b , c；

a = creat()；

b = creat()；

print(a)；

print(b)；

c = merge ( a , b)；

print(c)；

printf（“\n”）；

}

输入：ysplhd

zyxrmhb

输出：dhlpsy

bhmrxyz

zyyxsrpmlhhdb

2. 生成两个多项式PA和PB，求PA和PB之和，输出“和多项式”。解：typedef struct node

{int exp;

float coef;

struct node *next;

}polynode;

polynode *p,*q;

polynode *polyadd(pa,pb)

polynode *pa,*pb;

{polynode *p,*q,*pre,*r;

float x;

p=pa->next;

q=pb->next;

pre=pa;

while ((p!=NULL)&&(q!=NULL)) if (p->exp>q->exp)

{r=q->next;

q->next=p;

pre->next=q;

pre=q;

q=r;

}

else

if(p->exp==q->exp)

{x=p->coef+q->coef;

if (x!=0)

{p->coef=x;

s=p;

}

else

{pre->next=p->next; free(p);

}

p=pre->next;

r=p;

q=q->next;

free(r);

}

else

if (p->expexp)

{pre=p;

p=p->next;

}

}

if (q!=NULL)

pre->next=q;

free(pb);

}

3．设计一个统计选票的算法，输出每个候选的得票结果（假设采用单链表存放选票，候选人编号依次为1，2，3，……，N，且每张选票选且只选一人）

提示：以单链表存放选票，每个结点的data域存放该选票所选的候选人。用一个数组a统计得票结果。

typedef int elemtype；

typedef struct linknode

{

elemtype data；

struct linknode *next；

} nodetype；

nodetype *create()

{

elemtype d；

nodetype h=NULL,*s,*t；

int I=1；

printf（“建立一个单链表\n”）；

while (1)

{

printf（“输入第%d节点data域值：”,i)；

scanf（“%d”,&d)；

if (d= =0) break；

if(I= =1)

{

h=(nodetype *)malloc(sizeof(nodetype))；

h->data=d；h->next=NULL；t=h；

}

else

{

s=(nodetype *)malloc(sizeof(nodetype))；

s->data=d；s->next=NULL；t->next=s；

t=s；

}

I++；

}

return h；

}

void sat (nodetype *h, int a[])

{

nodetype *p=h；

while (p!=NULL)

{

a[p->data]++；

p=p->next；

数据结构课程设计题目及要求

实验一~实验四任选一题；实验五~实验九任选一题。 实验一运动会分数统计 一、实验目的： （1）熟练掌握线性表的两种存储方式 （2）掌握链表的操作和应用。 （3）掌握指针、结构体的应用 （4）按照不同的学校，不同项目和不同的名次要求，产生各学校的成绩单、团体总分报表。 二、实验内容： 【问题描述】 参加运动会的n个学校编号为1~n。比赛分成m个男子项目和w个女子项目，项目编号分别为1~m和m＋1~m＋w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。 【基本要求】 产生各学校的成绩单，内容包括各校所取得的每项成绩的项目号、名次（成绩）、姓名和得分；产生团体总分报表，内容包括校号、男子团体总分、女子团体总分和团体总分。 【测试数据】 对于n＝4，m＝3，w＝2，编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。 【实现提示】 可以假设m≤20，m≤30，w≤20，姓名长度不超过20个字符。每个项目结束时，将其编号、类型符（区分取前五名还是前三名）输入，并按名次顺序输入运动员姓名、校名（和成绩）。 【选作内容】 允许用户指定某些项目可采取其他名次取法。

实验二停车场管理 一、实验目的： （1）熟练掌握栈顺存和链存两种存储方式。 （2）掌握栈的基本操作及应用。 （3）以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。 二、实验内容： 【问题描述】 设停车场是一个可停放n辆汽车的长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车信放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场院，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 【基本要求】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。 【测试数据】 设n=2，输入数据为：(A，1，5)，（A，1，15），（A，3，20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。其中：A表示到达（Arrival）；D表示离去（Departure）；E表示输入结束（End）。 【实现提示】 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。 【选作内容】 （1）两个栈共享空间，思考应开辟数组的空间是多少？ （2）汽车可有不同种类，则他们的占地面积不同收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。（3）汽车可以直接从便道开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。 （4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。

数据库原理及应用(SQL Server 2008)全书答案 清华大学出版社 马建红 李占波主编第三章习题及实验答案

第三章习题及实验答案 习题答案 一、选择题 1、A 2、A 3、C 二、填空题 1、程序 2、MIN、SUM 3、CONTINUE、BREAK 三、简答题 1、可以使用的运算符可以分为算术运算符、逻辑运算符、赋值运算符、字符串串联运算符、按位运算符、一元运算符及比较运算符等。 2、用户自定义函数可分为：标量函数和表值函数。可使用CREATE FUNCTION语句创建函数，在调用用户自定义函数时，如果调用的是标量函数，则必须提供架构名。如果调用的是表值函数，则可以不提供架构名。用户可以将调用的函数用在赋值语句中，或作为表达式的操作数，或用在SQL命令中。 3、批处理是包含一个或多个Transaction-SQL语句的组，从应用程序一次性的发送到SQL Server执行。批处理是使用GO语句将多条SQL语句进行分隔，其中每两个GO之间的SQL 语句就是一个批处理单元。一个批处理中可以包含一条语句，也可以包含多条语句。 4、在SQL Server系统中，可以使用的流程控制语句有BEGIN…..END、IF…ELSE、CASE、WHILE…..CONTINUE….BREAK、GOTO、W AITFOR、RETURN等。 BEGIN…..END….: 在条件语句和循环语句等流程控制语句中，当符合特定条件需要执行两个或多个语句时，就应该使用BEGIN…END语句将这些语句组合在一起。 IF…..ELSE….: IF….ELSE语句是条件判断语句。 CASE:用于多重选择的条件判断语句，结果返回单个值。在CASE中可根据表达式的值选择相应的结果。 WHILE…..CONTINUE….BREAK: SQL语言中的循环语句，用来重复执行SQL语句或语句块。 GOTO: SQL程序中的无条件跳转语句，可以使程序直接跳到指定的标识符位置处继续执行。 WAITFOR: SQL中起暂停正在执行的语句、语句块或者存储过程的调用，直到某时间、时间间隔到达后才继续执行。 RETURN:用于无条件终止查询、存储过程或批处理。

数据结构实验报告-答案

数据结构(C语言版) 实验报告

专业班级学号姓名 实验1 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测 试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序： （1）增加插入结点的功能。 （2）将建立链表的方法改为头插入法。 程序代码: #include"" #include"" #include"" #include"" typedef struct node . . 示意图：

head head head 心得体会： 本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。另外实验指导书上给出的代码是有一些问题的，这使我们认识到实验过程中不能想当然的直接编译执行，应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。

实验2 实验题目：二叉树操作设计和实现 实验目的： 掌握二叉树的定义、性质及存储方式，各种遍历算法。 实验要求： 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历 的操作，求所有叶子及结点总数的操作。 实验主要步骤： 1、分析、理解程序。 2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针）， 如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求 所有叶子及结点总数。 实验代码 #include"" #include"" #include"" #define Max 20 ertex=a; irstedge=NULL; irstedge; G->adjlist[i].firstedge=s; irstedge; R[i] 留在原位

数据结构上机例题及答案

习题二 ⒉１描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点）。解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。 2.2简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。 解：顺序存储是按索引直接存储数据元素，方便灵活，效率高，但插入、删除操作将引起元素移动，降低了效率；而链式存储的元素存储采用动态分配，利用率高，但须增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入和删除十分简单。顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况；而链式存储适用于频繁进行元素动态插入或删除操作的场合。 2.3 在头结点为h的单链表中，把值为b的结点s插入到值为a的结点之前，若不存在a，就把结点s插入到表尾。 Void insert(Lnode *h,int a,int b) {Lnode *p,*q,*s; s=(Lnode*)malloc(sizeof(Lnode)); s->data=b; p=h->next; while(p->data!=a&&p->next!=NULL) {q=p; p=p->next; } if (p->data==a) {q->next=s; s->next=p;} else

{p->next=s; s->next=NULL; } } 2.4 设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B，使A中含有原链表中序号为奇数的元素，而B中含有原链表中序号为偶数的元素，并且保持元素原有的相对顺序。 Lnode *cf(Lnode *ha) {Lnode *p,*q,*s,*hb; int t; p=ha->next; q=ha; t=0; hb=(Lnode*)malloc(sizeof(Lnode)); s=hb; while(p->next!=NULL) {if (t==0) {q=p;p=p->next;t=1;} else {q->next=p->next; p->next=s->next; s->next=p; s=p; p=p->next; t=0; } } s->next=NULL; return (hb); }

数据库操作题及答案

数据库操作题及答案 【篇一：sql数据库复习资料操作题复习(带答案)】 本文件，文件名为学号姓名.sql，sql语句前加上题号。（共60分）一、创建数据库 创建一个数据库，数据库名为student，主数据文件的逻辑名为student_data,物理名称为student_data.mdf，存放在d盘根目录下，初始大小为10mb，最大可增长到50mb，增长方式是按5%比 例增长；日志文件的逻辑名称为student_log，物理名称为 student_log.ldf，存放在d盘根目录下，初始大小为2mb，最大可 增长到5mb，按1mb增长。 create database student on primary (name=student_data, filename=d:\student_data.mdf, size=10mb, maxsize=50mb, filegrowth=5%) log on (name=student_log, filename=d:\student_log.ldf, size=2mb, maxsize=5mb, filegrowth=1mb) 二、创建表 create table 学生 (学号 char(8) primary key, 姓名 char(20) not null, 性别 char(2) not null check(性别 in(男,女)),出生日期 datetime null) use student create table 成绩 (学号 char(8),课程名 varchar(30),成绩 real null check(成绩 between 0 and 100) primary key(学号,课程名), foreign key (学号) references 学生(学号)) 3、在gxc数据库中创建商品表，表名：sp。结构如下： use gxc create table sp (bh char(20) primary key,mc varchar(50) not null, xkc real, sj money) 4、在gxc数据库中创建供应表，表名：gy。结构如下： create table gy (ddh char(10),bh char(20) not null, sl float not null check(sl0), jg money, jsj datetime default(getdate()), primary key(ddh,bh), foreign key (bh) references sp(bh)) 5、往表中插入以下记录：

数据结构上机答案(c语言版)

实习一： 1、编写一个读入一个字符串，把它存入一个链表，并按相反的次序打印的程序。 2、设有一个单位的人员工资有如下信息：name、department、 base pay、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的base pay增加100元，增加后将工资数据显示于屏幕(每行1人)。请编写能够完成上述工作的程序。 代码如下： 1.#include #include #include void main() { char x; struct node //定义个结构node { char c; struct node *next; }; struct node *head,*pb,*pf,*p,*s,*t; //定义指针 printf("请输入字符串，按Enter结束！\n"); for(int i=0;x!='\n';i++) { pb=(struct node *)malloc(sizeof(struct node));//动态分配n字节的内存空间 scanf("%c",&pb->c); //输入字符 x=pb->c; if(i==0){ //输入的首个字符作为头结点pf head=pb; pf=head;} else if(pb->c!='\n'){ //如果输入的是Enter，输入终止，否则把字符依次存入链表 pf->next=pb; //把输入的字符pb存在pf后，pb后为空 pb->next=NULL;

经典数据结构上机题_答案解析

数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #include

#define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i

数据库技术与应用第5章 习题答案

第5章数据库完整性与安全性 1. 什么是数据库的完整性？什么是数据库的安全性？两者之间有什么区别和联系？ 解： 数据库的完整性是指数据库中数据的正确性、有效性和相容性，其目的是防止不符合语义、不正确的数据进入数据库，从而来保证数据库系统能够真实的反映客观现实世界。 数据库安全性是指保护数据库，防止因用户非法使用数据库造成数据泄露、更改或破坏。 数据的完整性和安全性是两个不同的概念，但是有一定的联系: 前者是为了防止数据库中存在不符合语义的数据，防止错误信息的输入和输出，即所谓垃圾进垃圾出所造成的无效操作和错误结果。后者是保护数据库防止恶意的破坏和非法的存取。也就是说，安全性措施的防范对象是非法用户和非法操作，完整性措施的防范对象是不合语义的数据。 2. 什么是数据库的完整性约束条件？完整性约束条件可以分为哪几类？ 解： 完整性约束条件是指数据库中的数据应该满足的语义约束条件。一般可以分为六类：静态列级约束、静态元组约束、静态关系约束、动态列级约束、动态元组约束、动态关系约束。静态列级约束是对一个列的取值域的说明，包括以下几个方面：①数据类型的约束，包括数据的类型、长度、单位、精度等；②对数据格式的约束；③对取值范围或取值集合的约束； ④对空值的约束；⑤其他约束。静态元组约束就是规定组成一个元组的各个列之间的约束关系，静态元组约束只局限在单个元组上。静态关系约束是在一个关系的各个元组之间或者若干关系之间常常存在各种联系或约束。常见的静态关系约束有：①实体完整性约束；②参照完整性约束；③函数依赖约束。动态列级约束是修改列定义或列值时应满足的约束条件，包括下面两方面：①修改列定义时的约束；②修改列值时的约束。动态元组约束是指修改某个元组的值时需要参照其旧值，并且新旧值之间需要满足某种约束条件。动态关系约束是加在关系变化前后状态上的限制条件，例如事务一致性、原子性等约束条件。 3. 试述DBMS如何实现完整性控制。 解： 为了维护数据库的完整性，DBMS提供了以下三种机制： ①完整性约束条件定义完整性约束条件也称为完整性规则，是数据库中的数据必须满足的语义约束条件。SQL标准使用了一系列概念来描述完整性，包括关系模型的实体完整性、参照完整性和用户定义完整性。这些完整性一般由SQL的DDL语义来实现。它们作为数据库模式的一部分存入数据字典中。 ②完整性检查方法检查数据是否满足已定义的完整性约束条件称为完整性检查。一般在INSERT、UPDATE、DELETE语句执行后开始检查，也可以在事务提交时检查。检查这些操作执行后数据库中的数据是否违背了完整性约束条件。 ③违约处理若发现用户操作违背了完整性约束条件，应采取一定的措施，如拒绝（NOACTION）执行该操作，或级连（CASCADE）执行其它操作，进行违约处理以保证数据的完整性。 4. 现有以下四个关系模式： 供应商（供应商编号，姓名，电话，地点），其中供应商编号为主码；

数据结构练习1

华东理工大学网络学院 《数据结构》（ch1绪论和ch2线性表） 班级 学号 姓名 成绩 一、 名词解释（每小题2分，共10分） 1.数据结构 2. 线性结构 3.存储结构 4. 逻辑结构 5.非线性结构 答：1.数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。 2. 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。 3. 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。 4. 逻辑结构：指数据元素之间的逻辑关系。 5.非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。 二、 填空题（每小题1分，共10分） 1. 非空的循环单链表head的尾结点p满足条件 p->next==head 。 2. 对于给定的n个数据元素，可能构造出集合 、线性结构 、 树形结构和网状（图形）结构四种逻辑结构。 3. 一个算法具有有穷性、 确定性 、 可行性 、输入和输出五个重要特性。 4. 在一个单链表中p所指结点之后插入s所指结点时,应执行s->next= p->next 和p->next= S 的操作。 三、判断正误（在正确的说法后面打勾，反之打叉）（每小题1分，共10分） （ × ）1. 线性数据结构只能用顺序结构存放，非线性数据结构只能用链式存储存放。 （ √ ）2. 单链表中逻辑上相邻的元素未必在存储的物理位置次序上相邻。 （ × ）3. 链式存储是一种随机存取的数据结构。 （ √ ）4 顺序表中逻辑上相邻的元素的物理位置必定相邻。 （ × ）5. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 （ √ ）6. 在顺序表中按下标序号访问任意一结点的时间复杂度均为O(1) 。 （ √ ）7. 带头结点的单向链表L为空的判定条件是L->next=null。 （ √ ）8. 在顺序表中插入或删除一个元素，需要平均移动表中一半元素。 （ × ）9. 线性表的逻辑顺序与存储顺序总是一致的。。 （ √ ）10. 任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。 四、单选题（每题2分，共30分） 1.有程序如下： i=1; k=0; while(i

数据结构上机考试题

注意事项1. 考试时间2小时，13：00-15：00 2. 题目4选2 3. 所有题目均使用标准输入和标准输出3. 只提交源程序，文件后缀名只能是.C或.CPP 4. 源文件大小不能超过10K，否则会被当作恶意提交而扣分5. 严格按照题目要求输出，去掉不需要的提示信息或调试信息6. 在程序中不要使用fflush(stdin)函数，否则会导致结果错误另外注意：本次是模拟测试，上机时间是4个小时，我们考试时间从14点开始到17点30分结束。同学视自己的能力，能做几道做几道。 哈夫曼树 时间限制: 100 second 内存限制: 100 Kb 描述 构造哈夫曼树（最优二叉树） 输入 输入n个结点每个结点的权值 输出 构造哈夫曼树（是最优二叉树）得到每个结点的哈夫曼编码 输入样例 23 186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 输出样例 1( 186):00 2( 64):1001 3( 13):101100 4( 22):110010 5( 32):11100 6( 103):011 7( 21):110001 8( 15):101101 9( 47):11010 10( 57):0101 11( 1):101111000 12( 5):10111101 13( 32):11101 14( 20):110000 15( 57):1010 16( 63):1000 17( 15):101110 18( 1):101111001 19( 48):11011 20( 51):0100 21( 80):1111 22( 23):110011 23( 8):1011111 提示 输入第一行是结点数23 第二行是这几个结点的权值输出格式为结点号（权值）：哈夫曼编码

数据结构上机考试(含答案)

《数据结构》上机练习题 1、设有两个有序序列，利用归并排序将它们排成有序表，并输出。 2、设有一有序序列，从键盘输入一个数，判别是否在序列中，如果在输出“YSE”；否则，将它插入到序列中使它仍然有序，并输出排序后的序列。 3、设有一有序序列，从键盘输入一个数，判别是否在序列中，如果不在，则输出“NO”，否则，将它从序列中删除它，并输出删除后的序列。 4、从键盘输入一组任意数据，建立一个有序链表，并从链头开始输出该链，使输出结果是有序的。 5、从键盘输入一组任意数据，建立一个包含所有输入数据的单向循环链表，并从链表的任意开始，依次输出该链表中的所有结点。 10、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在链表中，如果不在，则输出“NO“，否则，将它从链表中删除，并输出删除后的链表。 11、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在链表中，如果在输出“YSE”，否则，将它从插入到链头，并输出插入后的链表。 12、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在链表中，如果在输出“YSE”，否则，将它从插入到链尾，并输出插入后的链表。 13、编写栈的压栈push、弹栈pop函数，从键盘输入一组数据，逐个元素压入堆栈，然后再逐个从栈中弹出它们并输出。 14、编写栈的压栈push、弹栈pop函数，用它判别（）的匹配问题。 15、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树中序遍历的结果。 16、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树先序遍历的结果。 17、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树后序遍历的结果。 18、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树的总结点数。 19、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树叶子结点数。 20、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出此二叉树的高度。 21、给出一个无向图的邻接矩阵，输出各个顶点的度。 22、给出一个有向图的邻接矩阵，输出各个顶点的入度与出度。 23、输入一个有序序列，利用折半查找来查找一个数是否在序列中，如在，则输出其位置，否则输出“NO”。 24、用插入排序方法对一组数据进行排序，并输出每趟排序的结果。 25、用选择排序方法对一组数据进行排序，并输出每趟排序的结果。 26、用希尔（SHELL）排序方法对一组数据进行排序，并输出每趟排序的结果。 27、用快速排序方法对一组数据进行排序，并输出每趟排序的结果。． 答案： 1. #include #include #define N 5 #define NULL 0

数据库基本操作习题与答案

第三章数据库基本操作 一、选择题 1. 如果需要给当前表增加一个字段，应使用的命令是________。 A) APPEND B) INSERT C) EDIT D) MODIFY STRU 2. 设表文件及其索引已打开，为了确保指针定位在物理记录号为1的记录上，应该使用命令________。 A) SKIP 1 B) SKIP -1 C) GO 1 D) GO TOP 3. 要显示数据库中当前一条记录的内容，可使用命令________。 A) LIST B) BROWSE C) TYPE D) DISPLAY 4. 在当前表中，查找第2个女同学的记录，应使用命令________。 A) LOCATE FOR 性别="女" B) LOCATE FOR 性别="女" NEXT 2 C) LIST FOR 性别="女" CONTINUE D) LOCATE FOR 性别="女" CONTINUE 5. Visual FoxPro的数据库表之间可建立两种联系，它们是________。 A) 永久联系和临时联系B) 长期联系和短期联系 C) 永久联系和短期联系D) 长期联系和临时联系 6. 数据库表的索引中，字段值不能有重复的索引有________种。 A) 1 B) 2 C) 3 D) 4 7. 建立表间临时关联的命令是________。 A) LET RELATION TO命令 B) JOIN命令 C) SET RELATION TO命令 D) 以上都不是 8. 通过关键字建立表间的临时关联的前提是________。 A) 父表必须索引并打开B) 子表必须索引并打开 C) 两表必须索引并打开D) 两表都不必索引 9. 查询设计器的“筛选”选项卡上，“插入”按钮的作用是________。 A) 用于增加查询输出字段B) 用于增加查询的表 C) 用于增加查询去向D) 用于插入查询输出条件 10. 在多工作区的操作中，如果选择了4，7，8号工作区并打开了相应的数据库，在命令窗口执行命令SELECT 0，其功能是________。 A) 选择4号工作区为当前工作区B) 选择0号工作区为当前工作区 C) 选择7号工作区为当前工作区D) 选择8号工作区为当前工作区 11. 表结构中空值（NULL）的含义是________。 A) 空格B) 尚未确定

数据结构课程__课后习题答案

《数据结构简明教程》练习题及参考答案 练习题1 1. 单项选择题 （1）线性结构中数据元素之间是（）关系。 A.一对多 B.多对多 C.多对一 D.一对一 答：D （2）数据结构中与所使用的计算机无关的是数据的（）结构。 A.存储 B.物理 C.逻辑 D.物理和存储 答：C （3）算法分析的目的是（）。 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 答：C （4）算法分析的两个主要方面是（）。 A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 答：A （5）计算机算法指的是（）。 A.计算方法 B. 排序方法 C.求解问题的有限运算序列 D.调度方法答：C （6）计算机算法必须具备输入、输出和（）等5个特性。 A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 答：B 2. 填空题 （1）数据结构包括数据的①、数据的②和数据的③这三个方面的内容。 答：①逻辑结构②存储结构③运算

数据结构简明教程 （2）数据结构按逻辑结构可分为两大类，它们分别是①和②。 答：①线性结构②非线性结构 （3）数据结构被形式地定义为（D,R），其中D是①的有限集合，R是D上的②有限集合。 答：①数据元素②关系 （4）在线性结构中，第一个结点①前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点②后继结点，其余每个结点有且只有1个后继结点。 答：①没有②没有 （5）在树形结构中，树根结点没有①结点，其余每个结点有且只有②个前驱结点；叶子结点没有③结点，其余每个结点的后继结点数可以是④。 答：①前驱②1 ③后继④任意多个 （6）在图形结构中，每个结点的前驱结点数和后继结点数可以是（）。 答：任意多个 （7）数据的存储结构主要有四种，它们分别是①、②、③和④存储结构。 答：①顺序②链式③索引④哈希 （8）一个算法的效率可分为①效率和②效率。 答：①时间②空间 3. 简答题 （1）数据结构和数据类型两个概念之间有区别吗？ 答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素，而且还在其上定义了一组操作。 （2）简述线性结构、树形结构和图形结构的不同点。 答：线性结构反映结点间的逻辑关系是一对一的，树形线性结构反映结点间的逻辑关系是一对多的，图在结构反映结点间的逻辑关系是多对多的。 （3）设有采用二元组表示的数据逻辑结构S=(D,R)，其中D={a,b,…,i}，R={(a,b),(a,c),(c,d),(c,f),(f,h),(d,e),(f,g),(h,i)}，问相对于关系R，哪些结点是开始结点，哪些结点是终端结点？ 答：该逻辑结构为树形结构，其中a结点没有前驱结点，称为根结点，b、e、g、i结点没有后继结点，是终端结点，也称为叶子结点。 （4）以下各函数是算法中语句的执行频度，n为问题规模，给出对应的时间复杂度： T1(n)=n log2n-1000log2n T2(n)=3 log2 n-1000log2n

数据结构上机考试试题

数据结构上机考试试题（C++语言版） 考试要求：本次考试共列考核试题4大题，考生可以在所列4个考核试题中任选3个小题（即可能只属于2个大题），作为上机考核试题。 考核原则：所选题目在上机编程调试通过后即为考核通过。监考教师依据学生编程及调试通过与否情况给予考核成绩。 考核成绩评分标准： 所选3个题目全部编写出程序并调试通过：优 所选3个题目全部编写出程序，但只有2个上机调试通过：良 所选3个题目全部编写出程序，但只有1个上机调试通过：及格 所选3个题目全部编写出程序但都没有上机调试通过，或没有编写出全部程序：不及格。考核时间：2小时。 考核试题： 1、建立一个顺序方式存储的线性表，向表中输入若干元素后进行以下操作： （1）向线性表的表头、表尾或合适位置插入元素 （2）对线性表按升序或降序输出 2、建立一个动态链接方式存储的线性表，向表中输入若干元素后进行以下操作： （1）从单链表中查找指定元素 （2）返回单链表中指定序号的结点值 3、建立一个动态链接结构存储的二叉树，向这棵二叉树进行以下操作： （1）按任中序遍历次序输出二叉树中的所有结点 （2）求二叉树的叶子数 4、编写一个对整型数组A[n+1]中的A[1]至A[n]元素进行选择排序的算法，使得首先从待排序区间中选择出一个最大值并同最后一个元素交换，再从待排序区间中选择出一个最小值并同最第一个元素交换，反复进行直到待排序区间中元素的个数不超过1为止。 #include<> #include<> #include"" //初始化线性表 void InitList(LinearList& L, int ms) { =new ElemType[ms]; if(! { cerr<<"Memory allocation failure!"<

数据库上机实验题目和答案

试用SQL的查询语句表达下列查询： 1.检索王丽同学所学课程的课程号和课程名。 select Cno ,Cname from c where Cno in (select cno from sc where sno in (select sno from s where sname='王丽' )) 2.检索年龄大于23岁的男学生的学号和姓名。 select sno,sname from s where sex='男' and age>23 3.检索‘c01’课程中一门课程的女学生姓名 select sname from s where sex='女' and sno in (select sno from sc where cno='c01') 4.检索s01同学不学的课程的课程号。 select cno from c where cno not in (select cno from sc where sno ='s01') 5.检索至少选修两门课程的学生学号。 select sc.sno from s,sc where s.sno=sc.sno group by sc.sno having count(https://www.docsj.com/doc/1e10396286.html,o)>=2 6.每个学生选修的课程门数。 解法一： select so.sno sno,https://www.docsj.com/doc/1e10396286.html,ount,s.sname from(select sc.sno sno,count(sc.sno) ccount from sc,s where s.sno=sc.sno group by sc.sno ) so,s where s.sno=so.sno 解法二： select sc.sno sno,s.sname,count(sc.sno) ccount from sc,s where s.sno=sc.sno group by sc.sno,sname

数据结构实验一题目一线性表实验报告

数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 存储结构 带头结点的单链表

关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中 b、代码实现： Linklist::Linklist(int a[],int n)

堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)取链表长度函数 a、伪代码实现：判断该链表是否为空链表，如果是，输出长度0 如果不是空链表，新建立一个temp指针，初始化整形数n为0 将temp指针指向头结点 判断temp指针指向的结点的next域是否为空，如果不是，n加一，否 则return n 使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next 域为0，返回n b 、代码实现 void Linklist::Getlength()Linklist(); cout<

数据库上机习题及答案

数据库及应用复习题 一、设计题 有一个[学生课程]数据库，数据库中包括三个表： 学生表Student由学号(Sno)、姓名(Sname)、性别(Ssex)、年龄(Sage)、所在系(Sdept)五个属性组成，记为： Student(Sno,Sname,Ssex,Sage,Sdept) ，Sno 为关键字。 课程表Course由课程号(Cno)、课程名(Cname)、先修课号(Cpno)、学分(Ccredit)四个属性组成，记为：Course(Cno,Cname,Cpno,Ccredit) Cno为关键字。 成绩表SG由学号(Sno)、课程号(Cno)、成绩(Grade)三个属性组成，记为：SG(Sno,Cno,Grade) (SNO, CNO)为关键字。 用SQL语言实现下列功能： 1．建立学生表Student，其中学号属性不能为空，并且其值是唯一的。 2．向Student表增加“入学时间(Scome)”列，其数据类型为日期型。 3．查询选修了3号课程的学生的学号及其成绩，查询结果按分数的降序排列。4．查询学习1号课程的学生最高分数、平均成绩。 5．查询与“李洋”在同一个系学习的学生。 6．将计算机系全体学生的成绩置零。 7．删除学号为05019的学生记录。 8．删除计算机系所有学生的成绩记录。 1． CREATETABLE Student (Sno CHAR(5) NOT NULL UNIQUE, Sname CHAR(20), Ssex CHAR(2), Sage INT, Sdept CHAR(15)) 2． ALTER TABLE Student ADD Scome DATETIME 3． SELECT Sno, Grade FROM SG WHERE Cno='3' ORDER BY Grade DESC 4． SELECT MAX(Grade), AVG(Grade) FROM SC WHERE Cno='1' 5． SELECT Sno, Sname, Sdept FROM Student WHERE Sdept IN

数据结构实验题参考答案

【实验题】 1．狐狸逮兔子 围绕着山顶有10个圆形排列的洞，狐狸要吃兔子，兔子说：“可以，但必须找到我，我就藏身于这十个洞中，你先到１号洞找，第二次隔１个洞（即3号洞）找，第三次隔２个洞（即6号洞）找，以后如此类推，次数不限。”但狐狸从早到晚进进出出了1000次，仍没有找到兔子。问兔子究竟藏在哪个洞里？ （提示：这实际上是一个反复查找线性表的过程。） 【数据描述】 定义一个顺序表，用具有10个元素顺序表来表示这10个洞。每个元素分别表示围着山顶的一个洞，下标为洞的编号。 #define LIST_INIT_SIZE 10 //线性表存储空间的初始分配量 typedef struct { ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位） }SqList; 【算法描述】 status InitList_Sq(SqList &L) { //构造一个线性表L L.elem=(ElemType )malloc(LIST_INIT_SIZE*sizeof(ElemType)); If(!L.elem) return OVERFLOW; //存储分配失败 L.length=0; //空表长度为0 L.listsize=LIST_INIT_SIZE; //初始存储容量 return OK; } //InitList_Sq status Rabbit(SqList &L) { //构造狐狸逮兔子函数 int current=0; //定义一个当前洞口号的记数器，初始位置为第一个洞口 for(i=0;i #include #define OK 1 #define OVERFLOW -2 typedef int status; typedef int ElemType; #define LIST_INIT_SIZE 10 /*线性表存储空间的初始分配量*/