数据结构(计算机科学与技术)

1、数据结构（计算机科学与技术本科）第一部分 客观题 一、单项选择（每题 2 分，共 20分）1、设 n 为正整数。则下面程序段的时间复杂度为 。k=0;for（i=1;i=n;i+）for（j=i;jn ext;q = head;while (p != NULL & p-data n ext;p = (ListNode *)malloc(sizeof(ListNode);p-data = x;p_n ext = q_n ext;q_n ext = p;2、假设将循环队列定义为：以整型域变量front和length分别指示循环队列中队 头元素位置和队列中元素个数，指针 elem指示存放队列元素的连

2、续空间的首地 址，写出相应的入队列和出队列的算法。1. typedef char QElemType;2. typedefstruct3. QElemType elemMAXQSIZE;4. intlength;5. intrear;6. CLenQueue;7. Status EnCQueue(CLenQueue &Q, QElemType x)8. 9. if (Q.length = MAXQSIZE)10. return ERROR;/ 循环队列满11. 12. if (MAXQSIZE - 1 != Q.rear)13. +Q.rear;14. Q.elemQ.rear = x;15.

3、 16. else /rear 指向循环队列的末尾时，作特殊处理使其构成循环17. Q.rear = 0;18. Q.elemQ.rear = x;19. 20. +Q.length; /当前元素个数+121. return OK;22. 23.23. Status DeCQueue(CLenQueue &Q, QElemType &x)24. 25. if (!Q.length)26. return ERROR;/ 循环队列空27. 28. if (Q.rear + 1 = Q.length)/当rear的下标大于对头指向的下标时29. x = Q.elemQ.rear + 1 - Q.le

4、ngth;30. 31. else /当rear的下标小于队头下标时32. x = Q.elemMAXQSIZE + Q.rear + 1 - Q.length;33. 34. -Q.length; /当前元素个数-135. return OK;36. 37. #include 38. #include 39. #define QUEUE_SIZE 1040. /*循环队列结构体*/41. typedef struct 42. int front; /* 队列头 */43. int rear; /* 队列尾 */44. int len gth;/* 记录队列元素个数*/45. int data

5、QUEUE_SIZE; /*存放队列元素值的数组*/欢迎下载4Q-le ngth+; /*队列元素个数加1 */47.48.49.50.51.52.53.54.55.56.57.58.59.60.61.62.63.64.65.66.67.68.欢迎下载 CirQueue;/*初始化队列*/void ini tQueue(CirQueue *Q)Q_front = Q-rear = 0;Q-le ngth = 0;/*判断队列是否为空*/int QueueEmpty(CirQueue *Q)return Q-le ngth = 0;/*判断队列满*/int QueueFull(CirQueue

6、*Q)return Q-le ngth = QUEUE_SIZE;/*入队列*/void En Queue(CirQueue *Q, i nt data)if (QueueFull(Q)printf(队列已经满了 .n”);Q-dataQ-rear = data; /*将新元素插入队尾 */Q-rear = (Q-rea 叶1)%QUEUE_SIZE; /*将队尾加 1 */*岀队列*/int Dequeue(CirQueue *Q)int temp;if (QueueEmpty(Q)printf(队列已经为空!n”);temp = Q-dataQ-fro nt;Q-le ngth-; /*队

7、列元素个数减1 */Q-fro nt = (Q-fr on t+1)%QUEUE_SIZE; /*队列头加 1 */return temp;/*测试程序*/int mai n()CirQueue Q;intin put = 0; /*入队数据，由用户输入*/*初始化队列*/69.70.71.72.73.74.75.76.77.78.79.80.81.82.83.84.85.86.87.88.89.90.欢迎下载ini tQueue(&Q);691. printf(请输入入队数据:n);92. /*入队操作*/93. while(!QueueFull(&Q)94. 95. sea nf(%dn, &in put);96. En Queue(&Q, i nput);97. 98. printf(岀队数据:n);99. /